Deficiency (graph theory)

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 the set of red vertices U is the size of U minus the size of the set of all vertices that are neighbors of a vertex in U (the blue vertices)

Definition of deficiency

Let G = (V, E) be a graph, and let U be an independent set of vertices, that is, U is a subset of V in which no two vertices are connected by an edge. Let N_G(U) denote the set of neighbors of U, which is formed by all vertices from V that are connected by an edge to one or more vertices of U. The deficiency of the set U is defined by:

${\displaystyle \mathrm {def} _{G}(U):=|U|-|N_{G}(U)|}$

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

${\displaystyle \mathrm {def} (G;X):=\max _{U\subseteq X}\mathrm {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.

Deficiency and matchings

See also: Tutte's theorem on perfect matchings and Tutte–Berge formula

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:

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 original graph by removing the d dummy vertices; this leaves at most d vertices of X unmatched.

This theorem can be equivalently stated as:^[2]: 17

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

where ν(G) is the size of a maximum matching in G (called the matching number of G).

Properties of the deficiency function

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.

Strong Hall property

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]

Surplus

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.