Deficiency (graph theory)

The deficiency of the set of red vertices Template:Math is the size of Template:Math minus the size of the set of all vertices that are neighbors of a vertex in Template:Math (the blue vertices)

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.Template:Rp A related property is surplus.

Definition of deficiency

Let Template:Math be a graph, and let Template:Math be an independent set of vertices, that is, Template:Math is a subset of Template:Math in which no two vertices are connected by an edge. Let Template:Math denote the set of neighbors of Template:Math, which is formed by all vertices from Template:Math that are connected by an edge to one or more vertices of Template:Math. The deficiency of the set Template:Math is defined by:

${\mathrm{d}\mathrm{e}\mathrm{f}}_G(U):=|U|-|N_G(U)|$

Suppose Template:Math is a bipartite graph, with bipartition Template:Math. The deficiency of Template:Math with respect to one of its parts (say Template:Math), is the maximum deficiency of a subset of Template:Math:

$\mathrm{d}\mathrm{e}\mathrm{f}(G;X):=\underset{U\subseteq X}{max}{\mathrm{d}\mathrm{e}\mathrm{f}}_G(U)$

Sometimes this quantity is called the critical difference of Template:Math.

Note that Template:Math of the empty subset is Template:Math, so Template:Math.

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: Template:Math theorem

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:Template:Rp

$\nu (G)=|X|-\mathrm{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:Template:Rp

${\mathrm{def}}_G(X_1\cup X_2)+{\mathrm{def}}_G(X_1\cap X_2)\ge {\mathrm{def}}_G(X_1)+{\mathrm{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.Template:Rp

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:Template:Rp

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:

${\mathrm{sur}}_G(X_1\cup X_2)+{\mathrm{sur}}_G(X_1\cap X_2)\le {\mathrm{sur}}_G(X_1)+{\mathrm{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.Template:Rp

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.Template:Rp

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.Template:Rp

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.