Deficiency Measures an Obstruction to Matching
A matching can leave vertices exposed—that is, not incident with any edge of the matching. Deleting a set of vertices can reveal why some exposure is unavoidable: if the remaining graph has many odd components, each such component needs help from a deleted vertex to be fully matched. There are only so many deleted vertices available to provide that help. Deficiency formalizes this counting obstruction.
Throughout, graphs are finite and simple. A matching is a set of pairwise vertex-disjoint edges. A vertex not incident with any edge of a matching is exposed. For \(S\subseteq V(G)\), \(G-S\) is the subgraph induced by \(V(G)\setminus S\). A component is odd if it has an odd number of vertices. The empty graph has zero components, so its number of odd components is zero.
The maximum exists because a finite graph has finitely many vertex subsets. Also, \(\operatorname{def}(G)\ge 0\): taking \(S=\varnothing\) gives \(\operatorname{def}_G(\varnothing)=o(G)\ge0\). The value for a particular set \(S\) can be negative; it is the maximum over all sets that defines graph deficiency.
Why Deficiency Forces Exposed Vertices
Proof. Fix a set \(S\subseteq V(G)\) and a matching \(M\). Consider an odd component \(C\) of \(G-S\) that contains no exposed vertex. Every vertex of \(C\) is then matched. Since \(C\) has odd order, its vertices cannot all be paired with one another by edges of \(M\): a collection of disjoint edges internal to \(C\) covers an even number of its vertices. Thus at least one matching edge joins a vertex of \(C\) to a vertex outside \(C\). There are no edges between distinct components of \(G-S\), so that edge must join \(C\) to \(S\).
Different odd components of \(G-S\) with no exposed vertices require different vertices of \(S\): the matching edges are disjoint. Consequently, at most \(|S|\) odd components contain no exposed vertex. At least \(o(G-S)-|S|\) odd components therefore contain an exposed vertex, and different components contain different vertices. If this difference is negative, the fact that the number exposed is nonnegative still gives the same lower bound. Hence every matching \(M\) leaves at least \(\operatorname{def}_G(S)\) vertices exposed. This holds for every \(S\), so it holds in particular for a set attaining the maximum \(\operatorname{def}(G)\). \(\square\)
This theorem establishes a lower bound, not an automatic construction of a matching that attains it. To show that the bound is exact in a particular graph, one must also exhibit a matching with precisely that many exposed vertices.
Worked Example: The Star \(K_{1,3}\)
Let \(G\) have vertex set \(\{c,a,b,d\}\) and edge set \(\{ca,cb,cd\}\). To compute the maximum over all \(S\), let \(k\) be the number of leaves in \(S\), and separate the cases according to whether \(c\in S\). The three leaves are interchangeable, so these cases cover every subset.
| Is \(c\) in \(S\)? | \(k\) | \(o(G-S)\) | \(\operatorname{def}_G(S)\) |
|---|---|---|---|
| No | 0 | 0 | \(0-0=0\) |
| No | 1 | 1 | \(1-1=0\) |
| No | 2 | 0 | \(0-2=-2\) |
| No | 3 | 1 | \(1-3=-2\) |
| Yes | 0 | 3 | \(3-1=2\) |
| Yes | 1 | 2 | \(2-2=0\) |
| Yes | 2 | 1 | \(1-3=-2\) |
| Yes | 3 | 0 | \(0-4=-4\) |
For instance, when \(c\notin S\) and \(k=1\), the remaining graph is a three-vertex star, which is one odd component. When \(c\in S\) and \(k=0\), the three leaves remain as three isolated odd components. The largest table entry is \(2\), so \(\operatorname{def}(G)=2\). The theorem says every matching leaves at least two vertices exposed. The matching \(\{ca\}\) leaves \(b\) and \(d\) exposed, so the bound is attained.
Check: the graph has four vertices, and the matching \(\{ca\}\) covers two of them, leaving \(4-2=2\) exposed vertices, as claimed.
Parity and Disjoint Unions
Proof. For any graph \(H\), the total number of vertices is the sum of the orders of its components. Each even component contributes an even number; each odd component contributes an odd number. Therefore \(|V(H)|\) and \(o(H)\) have the same parity. Apply this to \(H=G-S\), whose order is \(|V(G)|-|S|\). It follows that \(o(G-S)-|S|\) has the same parity as \((|V(G)|-|S|)-|S|=|V(G)|-2|S|\), which has the same parity as \(|V(G)|\). Thus every value \(\operatorname{def}_G(S)\) has that parity. Their maximum has it as well. \(\square\)
The parity statement is a useful check on a calculation: a graph of even order must have even deficiency, and a graph of odd order must have odd deficiency. It does not determine the value by itself.
Proof. The vertex sets of \(H\) and \(K\) are disjoint, and there are no edges between them. Every set \(S\subseteq V(G)\) splits uniquely as \(S_H\cup S_K\), with \(S_H\subseteq V(H)\) and \(S_K\subseteq V(K)\). The components of \(G-S\) are exactly the components of \(H-S_H\) and \(K-S_K\). Hence \(\operatorname{def}_G(S)=\operatorname{def}_H(S_H)+\operatorname{def}_K(S_K)\). Each term is at most the corresponding graph deficiency, so every value on the left is at most \(\operatorname{def}(H)+\operatorname{def}(K)\). Conversely, choose sets \(S_H,S_K\) attaining the two maxima; their union attains the sum. This also covers an empty graph, whose only vertex subset is empty and whose deficiency is zero. \(\square\)
Worked Example: A Complete Bipartite Graph
Let \(G=K_{2,3}\) have parts \(A=\{a_1,a_2\}\) and \(B=\{b_1,b_2,b_3\}\), with all six edges \(a_i b_j\) for \(i\in\{1,2\}\) and \(j\in\{1,2,3\}\). For a set \(S\), let \(i=|S\cap A|\) and \(j=|S\cap B|\). The remaining graph is complete bipartite when both parts remain nonempty; if one part is empty, the remaining vertices are isolated. This gives all possible \(S\), grouped by \(i,j\):
| \(i\) | \(j\) | Odd components \(o(G-S)\) | \(\operatorname{def}_G(S)\) |
|---|---|---|---|
| 0 | 0 | 1 | \(1-(0+0)=1\) |
| 0 | 1 | 0 | \(0-(0+1)=-1\) |
| 0 | 2 | 1 | \(1-(0+2)=-1\) |
| 0 | 3 | 2 | \(2-(0+3)=-1\) |
| 1 | 0 | 0 | \(0-(1+0)=-1\) |
| 1 | 1 | 1 | \(1-(1+1)=-1\) |
| 1 | 2 | 0 | \(0-(1+2)=-3\) |
| 1 | 3 | 1 | \(1-(1+3)=-3\) |
| 2 | 0 | 3 | \(3-(2+0)=1\) |
| 2 | 1 | 2 | \(2-(2+1)=-1\) |
| 2 | 2 | 1 | \(1-(2+2)=-3\) |
| 2 | 3 | 0 | \(0-(2+3)=-5\) |
For example, at \((i,j)=(0,2)\), the remaining graph is \(K_{2,1}\), one component of order \(3\), so \(o(G-S)=1\). At \((2,0)\), the three vertices of \(B\) remain isolated, so \(o(G-S)=3\). The largest entry is \(1\), giving \(\operatorname{def}(G)=1\). The matching \(\{a_1b_1,a_2b_2\}\) exposes \(b_3\), so the lower bound is attained.
Check: this graph has five vertices, and the computed deficiency \(1\) is odd, in agreement with the parity proposition. The displayed matching has two edges and covers \(2\cdot2=4\) vertices, leaving \(5-4=1\) exposed.
Odd Cycles and a Deficiency of Two
Worked Example: The Disjoint Union of \(C_3\) and \(C_5\)
Let \(H\) be the cycle with vertex set \(\{1,2,3\}\) and edge set \(\{12,23,31\}\). Let \(K\) have vertex set \(\{a,b,c,d,e\}\) and edge set \(\{ab,bc,cd,de,ea\}\). Take \(G\) to be their disjoint union.
For either odd cycle \(C_n\), the choice \(S=\varnothing\) leaves one odd component, so \(\operatorname{def}_{C_n}(\varnothing)=1\). If \(S\) is nonempty and not all the vertices, deleting \(S\) leaves path components. There are at most \(|S|\) such components: each remaining path segment follows at least one deleted vertex as one goes around the cycle, and distinct segments have distinct preceding deleted vertices. Therefore \(o(C_n-S)\le |S|\), giving \(\operatorname{def}_{C_n}(S)\le0\). If \(S=V(C_n)\), then \(o(C_n-S)=0\) and \(\operatorname{def}_{C_n}(S)=-n\). Thus each of \(H\) and \(K\) has deficiency \(1\).
By the disjoint-union proposition, \(\operatorname{def}(G)=1+1=2\). The lower-bound theorem says every matching in \(G\) leaves at least two vertices exposed. A matching attaining this bound is \(\{12,ab,cd\}\); its exposed vertices are \(3\) and \(e\). It has three edges on eight vertices, so it covers \(2\cdot3=6\) vertices and leaves \(8-6=2\) exposed.
Using the Number Correctly
To calculate deficiency, count the odd components after deleting a candidate set and subtract the number of deleted vertices. The graph deficiency is the largest result over all sets—not the value for an arbitrarily chosen set. Symmetry can reduce the number of distinct cases, as in the star and complete bipartite examples, but the cases must still cover every subset.
A common mistake is to count all components rather than only the odd ones. In \(K_{2,3}\), taking \(S=\{b_1\}\) leaves \(K_{2,2}\), which is one component but has even order. Thus \(o(G-S)=0\) and \(\operatorname{def}_G(S)=0-1=-1\). Counting that component as odd would incorrectly give \(1-1=0\). Check the order of each component before adding it to \(o(G-S)\).
Once the maximum has been found, interpret it as a guarantee: no matching can leave fewer than that many vertices exposed. To claim that a matching leaves exactly that many, supply and check a matching of the required size. Deficiency gives the obstruction; the examples show how a matching can sometimes meet it.
Check Your Understanding
For each question, keep track of odd components specifically, and distinguish a lower bound from an exhibited matching.
- For the path with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\), compute \(\operatorname{def}_G(\{2\})\).
- Explain why \(\operatorname{def}(G)\) cannot be negative for any finite graph \(G\).
- A graph has seven vertices and deficiency \(3\). What parity check does this satisfy?
- For \(K_{1,4}\), compute \(\operatorname{def}_G(\{c\})\), where \(c\) is the center. What lower bound on exposed vertices follows?
- Why does finding a set \(S\) with \(\operatorname{def}_G(S)=2\) prove a lower bound of two exposed vertices, but not by itself prove that some matching leaves exactly two?