The Tutte-Berge Formula

From Odd Components to Exposed Vertices

A matching can cover many vertices, but some graphs force every matching to leave vertices uncovered. The obstruction is not simply the number of connected components: it is the number of odd components that remain after deleting a set of vertices. The Tutte–Berge formula says that the largest resulting excess of odd components over deleted vertices is exactly the number of vertices that every maximum matching must leave exposed.

Throughout, graphs are finite and simple. A matching in $G=(V,E)$ is a set of edges no two of which share an endpoint. A vertex is exposed by a matching if it is not an endpoint of any edge in that matching. A maximum matching is a matching with the largest possible number of edges; “maximum” here does not mean merely that no edge can be added while retaining a matching. Write $\nu(G)$ for the size of a maximum matching. If $M$ is a matching, it exposes $|V|-2|M|$ vertices, since each edge of $M$ covers exactly two distinct vertices.

Definition: For $S\subseteq V(G)$, $G-S$ is the graph obtained by deleting the vertices in $S$ and all edges incident with them. Let $o(G-S)$ be the number of connected components of $G-S$ that have an odd number of vertices. The matching deficiency of $G$ is the number of vertices exposed by a maximum matching: $$ \operatorname{def}(G)=|V(G)|-2\nu(G). $$

The empty graph has zero components, so its odd-component count is zero. We include every subset $S$, including $S=\varnothing$ and $S=V(G)$, when taking a maximum. The formula to be proved is

Theorem (Tutte–Berge): For every finite simple graph $G$, $$ \operatorname{def}(G)=\max_{S\subseteq V(G)}\bigl(o(G-S)-|S|\bigr). $$

In particular, the formula identifies a vertex set $S$ witnessing why a matching cannot cover all vertices: the odd components left after deleting $S$ can be joined to $S$ by matching edges only as many times as there are vertices in $S$. The proof has a lower-bound direction from this observation and an upper-bound direction obtained by adding dummy vertices.

Why Every Vertex Set Gives a Lower Bound

Lemma: For every matching $M$ in $G$ and every $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 all matching edges incident with vertices of $C$ have both endpoints in $C$. Such edges cover an even number of vertices, while $C$ has odd order, so at least one vertex of $C$ is exposed. A matching edge joining $C$ to $S$ can occur for at most $|S|$ different components: each such edge uses a distinct vertex of $S$. Thus at least $o(G-S)-|S|$ odd components have no matching edge to $S$, and each contributes a distinct exposed vertex. If this difference is negative, the claimed lower bound also holds because the number of exposed vertices is nonnegative. $\square$

Apply the lemma to a maximum matching and then maximize over all $S$. It gives one direction of the formula:

\operatorname{def}(G)\geq \max_{S\subseteq V(G)}\bigl(o(G-S)-|S|\bigr).

This direction does not require Tutte’s theorem. For the reverse inequality, we will show that a maximum value of the expression can be achieved as an upper bound on the number of exposed vertices.

Adding Universal Dummy Vertices

We use Tutte’s theorem, established earlier in the material on perfect matchings: a finite graph $H$ has a perfect matching if and only if $o(H-X)\leq |X|$ for every $X\subseteq V(H)$. Here a perfect matching covers every vertex. We will verify its condition for a particular augmentation of $G$.

Set $d=\max_{S\subseteq V(G)}(o(G-S)-|S|)$. This integer is nonnegative because the choice $S=\varnothing$ gives $o(G)\geq 0$. Also, $d$ and $|V(G)|$ have the same parity. Indeed, the sum of the orders of the components of $G-S$ is $|V(G)|-|S|$; modulo $2$, this sum equals the number $o(G-S)$ of odd-order components. Hence $o(G-S)-|S|$ is congruent to $|V(G)|$ modulo $2$, for every $S$, and so is its maximum $d$. Consequently $|V(G)|+d$ is even.

Form $H$ by adding $d$ new vertices, each adjacent to every other vertex of $H$. These are the universal dummy vertices. Edges of $G$ are retained, and the new vertices are distinct from the original vertices. We now check Tutte’s condition for every $X\subseteq V(H)$.

If $X$ contains all $d$ dummy vertices, write $X=S\cup D$, where $S\subseteq V(G)$ and $D$ is the set of dummy vertices. Then $H-X=G-S$, and the definition of $d$ gives $$ o(H-X)=o(G-S)\leq d+|S|=|X|. $$ This includes $d=0$, when the set of dummy vertices is empty.

Otherwise, at least one dummy vertex remains in $H-X$. If $H-X$ is nonempty, that remaining vertex is adjacent to every other remaining vertex, so $H-X$ is connected and has at most one odd component. When $X\ne\varnothing$, this gives $o(H-X)\leq 1\leq |X|$. When $X=\varnothing$, the graph $H$ itself is connected. Its order is even, as shown above, so it has zero odd components, and $o(H)=0=|X|$. If $H-X$ is empty, its odd-component count is zero, which also satisfies the condition. Thus $H$ satisfies Tutte’s condition in all cases.

Conclusion: Tutte’s theorem gives a perfect matching of $H$. Removing its edges incident with dummy vertices leaves a matching in $G$ that exposes at most $d$ original vertices.

To see the last claim, each original vertex exposed by the remaining matching must have been matched in the perfect matching of $H$ to a dummy vertex. There are only $d$ dummy vertices, and their matching edges have distinct endpoints. Therefore at most $d$ original vertices become exposed when the dummy vertices and their incident edges are removed. The resulting matching has size at least $(|V(G)|-d)/2$, so $\operatorname{def}(G)\leq d$. Together with the lower bound, this proves the formula.

Proof of the Tutte–Berge formula. The lemma shows that every maximum matching exposes at least $o(G-S)-|S|$ vertices for every $S$, hence $\operatorname{def}(G)\geq d$. The dummy-vertex construction and Tutte’s theorem produce a matching in $G$ exposing at most $d$ vertices, hence $\operatorname{def}(G)\leq d$. Therefore $\operatorname{def}(G)=d$. The argument also covers the empty graph: then $d=0$, the empty matching is perfect on the empty graph, and both sides equal zero. $\square$

Worked Examples

Worked Example: The Three-Vertex Path

Let $G$ have $V=\{1,2,3\}$ and $E=\{12,23\}$. The edge set $\{12\}$ is a matching, and no matching can have two edges because both available edges meet at vertex $2$. Thus $\nu(G)=1$, and the maximum matching exposes $3-2(1)=1$ vertex.

Now evaluate the expression in the formula. With $S=\varnothing$, $G-S$ is one component of order $3$, so $o(G-S)-|S|=1-0=1$. If $S=\{2\}$, the remaining vertices $1$ and $3$ are two isolated odd components, giving $2-1=1$. If $S=\{1\}$ or $S=\{3\}$, the remaining graph is a single edge, so the value is $0-1=-1$. For $|S|=2$, at most one vertex remains, so $o(G-S)\leq 1$ and the value is at most $1-2=-1$. For $S=V(G)$, it is $0-3=-3$. The maximum is $1$, agreeing with the number exposed.

Check: Here the maximum expression is $1$, so the formula gives $\nu(G)=(3-1)/2=1$, matching the direct matching calculation.

Worked Example: A Star with Four Leaves

Let $G$ have $V=\{c,1,2,3,4\}$ and $E=\{c1,c2,c3,c4\}$. Every edge uses $c$, so a matching has at most one edge; choosing $c1$ attains one edge. Thus $\nu(G)=1$, and $5-2(1)=3$ vertices are exposed by a maximum matching.

For $S=\varnothing$, the graph is one odd component, so the expression is $1-0=1$. For $S=\{c\}$, the four leaves become four isolated odd components, so the value is $4-1=3$. To bound the values for all other sets, put $k=|S|$. The graph $G-S$ has $5-k$ vertices, so $o(G-S)\leq 5-k$. Therefore $$ o(G-S)-|S|\leq (5-k)-k=5-2k. $$ For $k\geq 2$, this is at most $5-4=1$. For $k=1$, the only set giving the value $3$ is $S=\{c\}$, already evaluated; deleting a leaf leaves one odd component, giving $1-1=0$. Thus the maximum is $3$, attained at the center.

Check: The formula gives $\nu(G)=(5-3)/2=1$, consistent with the fact that all edges share $c$.

Worked Example: A Triangle and an Isolated Vertex

Let $G$ have $V=\{a,b,c,x\}$ and $E=\{ab,bc,ca\}$. The vertex $x$ is isolated. A matching in the triangle has at most one edge, and no edge is incident with $x$, so $\nu(G)=1$. A maximum matching therefore exposes $4-2(1)=2$ vertices.

For $S=\varnothing$, there are two odd components: the triangle and the isolated vertex. The expression is $2-0=2$. If $|S|=1$, deleting $x$ leaves one odd component, the triangle; deleting any triangle vertex leaves an edge and the isolated vertex, again with one odd component. In either case the value is $1-1=0$. If $k=|S|\geq 2$, then $G-S$ has $4-k$ vertices and $o(G-S)\leq 4-k$. Hence $$ o(G-S)-|S|\leq (4-k)-k=4-2k\leq 0. $$ So the maximum is $2$, as required.

Check: The formula gives $\nu(G)=(4-2)/2=1$. The isolated vertex cannot be matched, and at most one edge can be selected from the triangle.

Why the Formula Matters—and a Common Pitfall

The formula separates a matching problem into two parts: the matching size is encoded by a maximum over vertex sets, while each set is evaluated by counting odd components after deletion. A set $S$ attaining the maximum is often called a barrier. The dummy-vertex proof explains why the obstruction is exact: the set $S$ supplies too few vertices to connect all the odd components, and adding the precise deficiency in universal vertices restores the perfect-matching condition.

Common mistake: counting all components instead of odd components. For example, take $P_4$, with $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$, and delete $S=\{2\}$. The remaining graph has two components: the isolated vertex $1$, and the edge $34$. Only the first component is odd, so $o(G-S)=1$ and the expression is $1-1=0$. Counting both components would incorrectly give $2-1=1$. But $\{12,34\}$ is a perfect matching, so the deficiency is zero; the incorrect count contradicts the actual matching. The parity of a component—not just its existence—is essential.

Another useful check is parity: every value $o(G-S)-|S|$ has the same parity as $|V(G)|$, and so does the maximum deficiency. If a calculation produces the wrong parity, an odd component or a deleted vertex has been miscounted.

Check Your Understanding

Use the odd-component count and, where helpful, verify the answer by constructing or bounding a matching.

For the graph $V=\{1,2,3,4\}$, $E=\{12,23,34\}$, compute $o(G-S)-|S|$ for $S=\{1\}$.
For the star $K_{1,3}$, identify a set $S$ attaining the maximum in the Tutte–Berge formula and compute that maximum.
Explain why each odd component of $G-S$ with no matching edge to $S$ must contain an exposed vertex.
In the dummy-vertex proof, why does a perfect matching of the augmented graph leave at most $d$ original vertices exposed after dummy vertices are removed?
Why is $|V(G)|+d$ even when $d=\max_S(o(G-S)-|S|)$?

What You'll Learn