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.[1][2]: 17 A related property is surplus.
The deficiency of G with respect to one of its parts (say X), is the maximum deficiency of a subset of X: Sometimes this quantity is called the critical difference of G.[3] Note that defG of the empty subset is 0, so def(G;X) ≥ 0.
Hence, by Hall's marriage theorem, G admits a perfect matching.
Moreover, using the notion of deficiency, it is possible to state a quantitative version of Hall's theorem: Theorem — Every bipartite graph G = (X+Y, E) admits a matching in which at most def(G;X) vertices of X are unmatched.
A tight subset is a subset of X whose deficiency equals the deficiency of the entire graph (i.e., equals the maximum).
[2]: Lem.1.3.3 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).
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.
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.
[2]: Lem.1.3.5 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 NG(x), the resulting graph has a non-negative surplus.
[2]: Thm.1.3.6 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.
X) if-and-only-if it contains a forest F such that every vertex in X has degree 2 in F.[2]: Thm.1.3.8 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.