Let G = be a graph, and let U be an independent set of vertices - a subset of V in which no two vertices are connected by an edge. Denote by NG the set of neighbors of U - a subset of V that contains all vertices that are connected by an edge to one or more vertices of U. The deficiency of the set U is defined by:
defG := |U| - |NG|
Suppose G is a bipartite graph, with bipartition V = X u Y. The deficiency of Gwith respect to one of its parts, is the maximum deficiency of a subset of X:
If def = 0, it means that for all subsetsU of X, |NG| ≥ |U|. Hence, by Hall's marriage theorem, G admits a perfect matching. In contrast, if def > 0, it means that for some subsets U of X, |NG| < |U|. Hence, by the same theorem, G does not admit a perfect matching. Moreover, using the notion of deficiency, it is possible to state a quantitative version of Hall's theorem:
Every bipartite graph G = admits a matching in which at most def vertices of X are unmatched.
Proof. Let d = def. This means that, for every subset U of X, |NG| ≥ |U|-d. Add d dummy vertices to Y, and connect every dummy vertex to all vertices of X. After the addition, for every subset U of X, |NG| ≥ |U|. By Hall's marriage theorem, the new graph admits a matching in which all vertices of X are matched. Now, restore the origial graph by removing the d dummy vertices; this leaves at most d vertices of X unmatched. Other ways to state this theorem are: where ν the is size of a maximum matching in G.
Properties of the deficiency function
In a bipartite graph G =, the deficiency function is a supermodular set function: for every two subsets X1, X2 of X:A tight subset is a subset of X whose deficiency equals the deficiency of the entire graph. The intersection and union of tight sets are tight; this follows from properties of upper-bounded supermodular set functions. In a non-bipartite graph, the deficiency function is, in general, not supermodular.
A graph G has the Hall property if Hall's marriage theorem holds for that graph, namely, if G has either a perfect matching or a vertex set with a positive deficiency. A graph has the strong Hall property if def = |V| - 2 ν. Obviously, the strong Hall property implies the Hall property. Bipartite graphs have both of these properties, however there are classes of non-bipartite graphs that have these properties. In particular, a graph has the strong Hall property if-and-only-if it is stable - its maximum matching size equals its maximum fractional matching size.
Surplus
The surplus of a subset U of V is defined by:
surG := |NG| - |U| = - defG
The surplus of a graph G w.r.t. a subset X is defined by the minimum surplus of non-empty subsets of X:
sur := min surG
Note the restriction to non-empty subsets: without it, the surplus of all graphs would always be 0. Note also that:
def = max
In a bipartite graph G =, the surplus function is a submodular set function: for every two subsets X1, X2 of X:A surplus-tight subset is a subset of X whose surplus equals the surplus of the entire graph. The intersection and union of tight sets with non-empty intersection are tight; this follows from properties of lower-bounded submodular set functions. For a bipartite graph G with def = 0, the number sur is the largest integer s satisfying the following property for every vertex x in X: if we add s new vertices to X and connect them to the vertices in NG, the resulting graph has a non-negative surplus. If G is a bipartite graph with a positive surplus, such that deleting any edge from G decreases sur, then every vertex in X has degree sur+1. A bipartite graph has a positive surplus if-and-only-if it contains a forest F such that every vertex in X has degree 2 in F. Graphs with a positive surplus play an important role in the theory of graph structures; see the Gallai–Edmonds decomposition. In a non-bipartite graph, the surplus function is, in general, not submodular.
