Deficiency (graph theory)

Short description: Refinement of perfect matching theorems

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.

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) denotes 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:

[math]\displaystyle{ \mathrm{def}_G(U) := |U| - |N_G(U)| }[/math]

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:

[math]\displaystyle{ \mathrm{def}(G;X) := \max_{U\subseteq X} \mathrm{def}_G(U) }[/math]

Sometimes this quantity is called the critical difference of G.

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

Deficiency and matchings

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:

[math]\displaystyle{ \nu(G) = |X| - \operatorname{def}(G;X), }[/math]

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:

[math]\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) }[/math]

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.

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.

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:

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:

[math]\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) }[/math]

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_G(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.