Unsaturated vertex

Unsaturated vertex --- свободная вершина.

1. See Unary node.

2. A vertex [math]\displaystyle{ v }[/math] is unsaturated by a matching [math]\displaystyle{ M }[/math], if there is no edge of [math]\displaystyle{ M }[/math] incident with [math]\displaystyle{ v }[/math]. A matching [math]\displaystyle{ M }[/math] is called 1-factor (or a perfect matching), if there is no vertex of the graph unsaturated by [math]\displaystyle{ M }[/math].

The deficiency [math]\displaystyle{ def(G) }[/math] of [math]\displaystyle{ G }[/math] is the number of vertices unsaturated by a maximum matching of [math]\displaystyle{ G }[/math]. Observe that [math]\displaystyle{ def(G) = |V| - 2|M| }[/math] for any maximum matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math].