Deficiency (graph theory)

Let G = (V, E) 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 N_G(U) 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:

def_G(U) := |U| - |N_G(U)|

Suppose G is a bipartite graph, with bipartition V = X u Y. The deficiency of G with respect to one of its parts (say X), is the maximum deficiency of a subset of X:

def(G;X) := max [U subset of X] def_G(U)

Sometimes this quantity is called the critical difference of G.[3]

Note that def_G of the empty subset is 0, so def(G;X) ≥ 0.

If def(G;X) = 0, it means that for all subsets U of X, |N_G(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_G(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:

Every bipartite graph G = (X+Y, E) admits a matching in which at most def(G;X) vertices of X are unmatched.

Proof. Let d = def(G;X). This means that, for every subset U of X, |N_G(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_G(U)| ≥ |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:[2]^:17

${\displaystyle \nu (G)=|X|-\operatorname {def} (G;X)}$

where ν(G) the is size of a maximum matching in G (also 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₁, X₂ of X:[2]^:Lem.1.3.2

${\displaystyle \operatorname {def} _{G}(X_{1}\cup X_{2})+\operatorname {def} _{G}(X_{1}\cap X_{2})\geq \operatorname {def} _{G}(X_{1})+\operatorname {def} _{G}(X_{2})}$

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.[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). 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.[3]

The surplus of a subset U of V is defined by:

sur_G(U) := |N_G(U)| - |U| = - def_G(U)

The surplus of a graph G w.r.t. a subset X is defined by the minimum surplus of non-empty subsets of X:[2]^:19

sur(G;X) := min [U a non-empty subset of X] sur_G(U)

Note the restriction to non-empty subsets: without it, the surplus of all graphs would always be 0. Note also that:

def(G;X) = max[0, - sur(G; X)]

In a bipartite graph G = (X+Y, E), the surplus function is a submodular set function: for every two subsets X₁, X₂ of X:

${\displaystyle \operatorname {sur} _{G}(X_{1}\cup X_{2})+\operatorname {sur} _{G}(X_{1}\cap X_{2})\leq \operatorname {sur} _{G}(X_{1})+\operatorname {sur} _{G}(X_{2})}$

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 N_G(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.[4]

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.[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.