Deficiency is a concept in graph theory that is used to refine various theorems related to perfect matching in graphs, such as Hall's marriage theorem. This was first studied by ÃÂystein Ore. A related property is surplus.
Let be a graph, and let be an independent set of vertices, that is, is a subset of in which no two vertices are connected by an edge. Let denote the set of neighbors of , which is formed by all vertices from that are connected by an edge to one or more vertices of . The deficiency of the set is defined by:
Suppose is a bipartite graph, with bipartition . The deficiency of with respect to one of its parts (say ), is the maximum deficiency of a subset of :
Sometimes this quantity is called the critical difference of .
Note that of the empty subset is , so .
If def(G;X) = 0, it means that for all subsets U of X, |N<sub>G</sub>(U)| âÂÂ¥ |U|. Hence, by Hall's marriage theorem, G admits a perfect matching.
In contrast, if def(G;X) > 0, it means that for some subsets U of X, |N<sub>G</sub>(U)| < |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:
Proof. Let d = def(G;X). This means that, for every subset U of X, |N<sub>G</sub>(U)| âÂÂ¥ |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, |N<sub>G</sub>(U)| âÂÂ¥ |U|. By Hall's marriage theorem, the new graph admits a matching in which all vertices of X are matched. Now, restore the original graph by removing the d dummy vertices; this leaves at most d vertices of X unmatched.
This theorem can be equivalently stated as:
where ý(G) is the size of a maximum matching in G (called the matching number of G).
In a bipartite graph G = (X+Y, E), the deficiency function is a supermodular set function: for every two subsets X<sub>1</sub>, X<sub>2</sub> of X:<blockquote></blockquote>A tight subset is a subset of X whose deficiency equals the deficiency of the entire graph (i.e., equals the maximum). 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(G) = |V| - 2 ý(G). 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.
The surplus of a subset U of V is defined by:<blockquote>sur<sub>G</sub>(U) := |N<sub>G</sub>(U)| â |U| = âÂÂdef<sub>G</sub>(U)</blockquote>The surplus of a graph G w.r.t. a subset X is defined by the minimum surplus of non-empty subsets of X: <blockquote>sur(G;X) := min [U a non-empty subset of X] sur<sub>G</sub>(U)</blockquote>Note the restriction to non-empty subsets: without it, the surplus of all graphs would always be 0. Note also that:<blockquote>def(G;X) = max[0, âÂÂsur(G; X)]</blockquote>In a bipartite graph G = (X+Y, E), the surplus function is a submodular set function: for every two subsets X<sub>1</sub>, X<sub>2</sub> of X:<blockquote></blockquote>A surplus-tight subset is a subset of X whose surplus equals the surplus of the entire graph (i.e., equals the minimum). 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(G;X) = 0, the number sur(G;X) 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 N<sub>G</sub>(x), 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(G;X), then every vertex in X has degree sur(G;X) + 1.
A bipartite graph has a positive surplus (w.r.t. X) 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.