Deficiency of a graph

Deficiency of a graph --- дефицит графа.

Let [math]\displaystyle{ M }[/math] be a matching in a graph [math]\displaystyle{ G }[/math]. A vertex [math]\displaystyle{ v }[/math] is saturated by [math]\displaystyle{ M }[/math] if an edge of [math]\displaystyle{ M }[/math] is incident with [math]\displaystyle{ v }[/math], otherwise [math]\displaystyle{ v }[/math] is said to be unsaturated.

The deficiency [math]\displaystyle{ def(G) }[/math] of the graph [math]\displaystyle{ G }[/math] is the number of vertices unsaturated by a maximum matching. Thus, if [math]\displaystyle{ def(G) = 0 }[/math], then [math]\displaystyle{ G }[/math] has a perfect matching.