Maximum Matchings From Tutte-Berge

From Odd Components to Matching Bounds

A matching can leave vertices uncovered, and some graphs force it to leave more vertices uncovered than parity alone would suggest. The Tutte-Berge formula measures this obstruction by deleting a set of vertices and counting the odd components that remain. In applications, the formula gives an upper bound on the size of a maximum matching; a matching that reaches that bound certifies the exact answer.

All graphs in this tutorial are finite and simple. A matching $M$ is a set of edges no two of which share a vertex. A vertex is exposed by $M$ if it is incident with no edge of $M$. Write $\nu(G)$ for the maximum size of a matching in $G$, and $o(H)$ for the number of connected components of a graph $H$ that have an odd number of vertices. For $S\subseteq V(G)$, $G-S$ is the subgraph induced by the vertices outside $S$.

Theorem (Tutte-Berge formula): For every finite graph $G$ of order $n=|V(G)|$, $$ \nu(G)=\frac{n-\operatorname{def}(G)}{2}, \qquad \operatorname{def}(G)=\max_{S\subseteq V(G)}\bigl(o(G-S)-|S|\bigr). $$ The quantity $\operatorname{def}(G)$ is the deficiency of $G$. The formula is a standard result established in the earlier material on the Tutte-Berge formula; here we use it to calculate and certify maximum matching sizes.

The maximum over all sets $S$ matters. A particular choice of $S$ provides a lower bound on the deficiency, and therefore an upper bound on $\nu(G)$. It does not, by itself, prove that the bound is sharp. To establish the exact maximum matching size, pair the bound with a matching of that size.

Why Odd Components Force Exposed Vertices

Proposition: For every matching $M$ in $G$ and every set $S\subseteq V(G)$, the number of vertices exposed by $M$ is at least $o(G-S)-|S|$.

Proof. Consider an odd component $C$ of $G-S$. If no edge of $M$ joins a vertex of $C$ to a vertex of $S$, then the vertices of $C$ can only be matched to other vertices of $C$. Since $|V(C)|$ is odd, edges internal to $C$ cannot cover all its vertices: each matching edge covers two vertices, and an odd number is not divisible by two. Thus $C$ contains an exposed vertex. Consequently, any odd component that contains no exposed vertex must have a matching edge joining it to $S$.

Different components that have matching edges to $S$ use different vertices of $S$. Indeed, matching edges cannot share an endpoint. There are therefore at most $|S|$ such components. Among the $o(G-S)$ odd components, at least $o(G-S)-|S|$ contain exposed vertices. These vertices lie in disjoint components, so they are distinct. If this difference is negative, the asserted lower bound is automatic because the number of exposed vertices is nonnegative. This proves the proposition. $\square$

If $M$ has $k$ edges, it covers exactly $2k$ vertices, so it exposes $n-2k$ vertices. The proposition therefore gives, for every $S\subseteq V(G)$,

n-2|M|\ge o(G-S)-|S|, \qquad |M|\le \frac{n-o(G-S)+|S|}{2}.

Taking the strongest of these bounds over all $S$ is equivalent to the Tutte-Berge formula. For practical certification, however, it is often enough to find one useful $S$ and then exhibit a matching that meets its bound.

Certificate principle: If $M$ is a matching with $k$ edges and $S\subseteq V(G)$ satisfies $o(G-S)-|S|=n-2k$, then $M$ is maximum. The deletion set certifies that every matching leaves at least $n-2k$ vertices exposed, while $M$ exposes exactly that many.

Proof. The proposition applied to $S$ says that every matching $N$ exposes at least $o(G-S)-|S|=n-2k$ vertices. If $N$ has $j$ edges, it exposes $n-2j$ vertices, so $n-2j\ge n-2k$, which implies $j\le k$. Since $M$ has $k$ edges, no matching is larger, and $M$ is maximum. $\square$

Worked Certificates

Worked Example: A Star with Four Leaves

Let $G$ have $V(G)=\{c,1,2,3,4\}$ and $E(G)=\{c1,c2,c3,c4\}$. Take $S=\{c\}$. After deleting $c$, the four remaining vertices are four isolated components, each of order $1$, so $o(G-S)=4$. Hence

$$ o(G-S)-|S|=4-1=3. $$

Every matching must therefore expose at least $3$ of the $5$ vertices, and it can have at most $(5-3)/2=1$ edge. The edge set $M=\{c1\}$ is a matching of size $1$; it exposes $2,3,4$, exactly $3$ vertices. Thus $\nu(G)=1$. In fact, the four maximum matchings are $\{c1\},\{c2\},\{c3\},\{c4\}$, one for each choice of leaf. The exposed-vertex certificate applies to all four.

Check: The matching $\{c1\}$ covers $c$ and $1$, so the number exposed is $5-2(1)=3$, agreeing with the certificate.

Worked Example: A Complete Bipartite Graph

Let $G$ have $V(G)=\{a,b,x,y,z\}$ and $E(G)=\{ax,ay,az,bx,by,bz\}$, so every edge joins one of $a,b$ to one of $x,y,z$. Choose $S=\{a,b\}$. The graph $G-S$ consists of the three isolated vertices $x,y,z$. Thus $o(G-S)=3$, $|S|=2$, and

$$ o(G-S)-|S|=3-2=1. $$

Every matching exposes at least $1$ of the $5$ vertices. Its size is at most $(5-1)/2=2$. The set $M=\{ax,by\}$ is a matching of size $2$, leaving $z$ exposed, so $\nu(G)=2$.

There are $6$ maximum matchings: choose which two of $x,y,z$ are matched, in $3$ ways, and then assign the chosen vertices to $a,b$, in $2$ ways. The product is $3\cdot2=6$. Each such matching covers $a,b$ and two of the three other vertices, so it exposes exactly one vertex and attains the lower bound.

Check: The displayed matching has two edges with four distinct endpoints, hence is valid. Since the certificate bounds every matching by $2$ edges, none of the six, or any other matching, can be larger.

Worked Example: Several Maximum Matchings in a Disconnected Graph

Let $G$ have $V(G)=\{1,2,3,4,5,6,7\}$ and $E(G)=\{12,23,34,41,56,67,75\}$. Its components are the 4-cycle on $\{1,2,3,4\}$ and the triangle on $\{5,6,7\}$. Take $S=\varnothing$. The 4-cycle is an even component, and the triangle is one odd component, so $o(G-S)=1$. It follows that

o(G-S)-|S|=1-0=1, \qquad |M|\le \frac{7-1}{2}=3.

The matching $M=\{12,34,56\}$ has three edges with no shared endpoints, so it reaches the upper bound and $\nu(G)=3$. It exposes vertex $7$. There are two ways to match all four vertices of the cycle: $\{12,34\}$ or $\{23,41\}$. In the triangle, a matching has one edge, with three choices: $56$, $67$, or $75$. Combining these choices gives $2\cdot3=6$ matchings of size $3$. Each is maximum, since the certificate rules out every matching of size $4$.

Check: A size-$3$ matching covers $2(3)=6$ vertices, so it exposes $7-6=1$, as required by the bound. The six matchings counted above are distinct because each has a distinct choice of cycle edges, triangle edge, or both.

Using the Formula Carefully

For a set $S$, the number $o(G-S)-|S|$ measures a specific obstruction: many odd components remain, but there are too few deleted vertices to match one vertex from each of them. The proposition proves that at least the excess number of odd components must contribute exposed vertices. Since each matching edge covers two vertices, an exposed-vertex lower bound becomes a matching-size upper bound.

To use this reasoning efficiently, first propose a set $S$ whose deletion breaks the graph into many odd components. Compute the component orders and count only those that are odd. Then calculate $o(G-S)-|S|$, convert it to a bound on matching size, and finally exhibit a matching meeting that bound. The last step is essential: an upper bound alone does not establish that a matching of that size exists.

The formula also includes degenerate cases. For the empty graph, $n=0$, the only choice is $S=\varnothing$, and $o(G-S)=0$; the formula gives $\nu(G)=0$. For a graph with isolated vertices, each isolated vertex is an odd component unless it is deleted into $S$, so these vertices are naturally counted in the same calculation.

Common Pitfall: One Set Is Not the Maximum

Consider the star from the first example, but choose $S=\varnothing$. The whole graph is one component of order $5$, so this choice gives $o(G-S)-|S|=1-0=1$, and therefore only the bound $|M|\le(5-1)/2=2$. That bound is valid, but it is not sharp: the actual maximum is $1$. Choosing $S=\{c\}$ gives $4-1=3$ and the sharp bound $|M|\le1$.

A wrong calculation would treat the value from $S=\varnothing$ as the deficiency and conclude $\nu(G)=2$. The correction is that the deficiency is the maximum of $o(G-S)-|S|$ over every $S$, not its value for an arbitrary choice. Alternatively, the certificate method avoids computing that maximum: use $S=\{c\}$ to get the upper bound $1$, then exhibit a one-edge matching.

The exact number of exposed vertices in a maximum matching is $\operatorname{def}(G)$, by the Tutte-Berge formula and the identity $n-2\nu(G)=\operatorname{def}(G)$. Thus a useful deletion set does more than suggest that some vertices must be left unmatched: when its bound is attained, it certifies the maximum matching size.

Check Your Understanding

For each question, distinguish a bound obtained from a chosen set $S$ from an exact maximum matching size.

Let $G$ have $V(G)=\{a,b,c,d\}$ and $E(G)=\{ab,bc,cd\}$. Use $S=\{b\}$ to calculate an exposed-vertex lower bound and a matching-size upper bound.
In the graph of Question 1, exhibit a matching that reaches the bound from $S=\{b\}$, and use the certificate principle to determine $\nu(G)$.
Let $G$ have vertices $\{1,2,3,4,5,6\}$ and edges $\{12,23,31,45,56,64\}$. Use $S=\varnothing$ to bound the maximum matching size, and exhibit a matching meeting that bound.
Explain why $o(G-S)-|S|$ is a lower bound on exposed vertices even when its value is negative.
For the star with four leaves, compare the bound from $S=\varnothing$ with the bound from $S=\{c\}$. Which one certifies the maximum matching size?