Tutte's Theorem

Lemma (Tutte’s: Parity of V)

Suppose that $\forall S\subset V,|S|\ge \Omega (G-S)$¹. We know $|V|$ must be even. This is because we can have $S=\varnothing$ such that

$$0=|S|\ge \Omega (G-S)=\Omega (G)\ge 0$$

implying that all connected components $C$ are even. Indeed,

$$|V|=\sum _{\text{CCs}}\mathrm{deg}(C)$$

where a sum of even components is even.

Lemma (Parity of Cut and Components)

For any $S\subset V,|S|-\Omega (G-S)$ is even.

Proof: Since $|V|$ must be even, then

$$|V|=|S|+\sum _{\begin{array}{c}\text{CCs }C\\ \text{of }G-S\end{array}}|C|$$

Using modular arithmetic, if $|C|$ is even then $|C|\equiv 0\mathrm{mod}2$ and if $|C|$ is even, $|C|\equiv 1\mathrm{mod}2$. Indeed,

$$\sum |C|\equiv \Omega (G-S)\mathrm{mod}2$$

and as $|V|\equiv 0\mathrm{mod}2$,

$$\begin{array}{rl}|V|& =|S|+\sum _{\begin{array}{c}\text{CCs }C\\ \text{of }G-S\end{array}}|C|\\ 0& \equiv [|S|+\Omega (G-S)]\mathrm{mod}2\end{array}$$

Implying that $|S|$ and $\Omega (G-S)$ have the same parity. Indeed,

$$|S|-\Omega (G-S)\equiv 0\mathrm{mod}2$$

which completes the lemma proof.

Corollary (Tutte Condition)

If $|S|>\Omega (G-S)$, then $|S|\ge \Omega (G-S)+2$, which comes from the lemma.

Tutte’s Theorem

The Bipartite Graph $G=(V,E)$ has a perfect matching $⟺\forall S\subset V,|S|\ge \Omega (G-S)$¹.

Proof:

$(⟹)$ Let $G$ have a perfect matching. If by contradiction that $\exists S\subset V$ where $|S|<\Omega (G-S)$, then if $C$ is an odd connected component of $G-S$, then $C$ has no internal perfect matching because at least one vertex will be unpaired.

Let this be $v\in C$. Then $v$ must match to some $w\in (G-S)-C$. As $C$ is a connected component of $C-S$, $C$ cannot bridge to another connected component, and thus must bridge to $S$ in $G$. Indeed, $w\in S$.

This is true for all odd connected components. Thus, there are at least $\Omega (G-S)$ total $w\in S$, such that

$$|S|\ge \Omega (G-S)$$

which is a contradiction.

$(⟸)$ Suppose $\forall S\subset V,|S|\ge \Omega (G-S)$. From Lemma (Tutte’s Parity of V), $|V|$ must be even.

We proceed with strong induction. If $|V|=2$, then this is trivial. Assume for any graph with strictly less than $m$ vertices, the theorem holds. We want to show that for graph $G$ with $m$ vertices, it has a perfect matching.

Case 1: Suppose that for all nonempty subsets $S\subseteq V$ the strict inequality $|S|>\Omega (G-S)$ holds. From Corollary (Tutte Condition), then $|S|\ge \Omega (G-S)+2$.

We can pick an arbitrary edge $e=(u,v)$ and consider $G^{\prime }=G-\{u,v\}$. We need to show it satisfies the Tutte Condition to apply IH. Suppose it does not, such that $\exists S\subseteq V(G^{\prime })$ such that

$$|S|<\Omega (G^{\prime }-S).$$

Take $S^{\prime }=S\cup \{u,v\}$ in $G$. This tells us that

$$|S^{\prime }|=|S|+2$$

Indeed, $G-S^{\prime }$ is isomorphic to $G^{\prime }-S$ (we remove the same vertices) such that

$$\Omega (G-S^{\prime })=\Omega (G^{\prime }-S)$$

By substitution,

$$\begin{array}{rl}|S|& <\Omega (G^{\prime }-S)\\ |S^{\prime }|-2& <\Omega (G-S^{\prime })\\ |S^{\prime }|& <\Omega (G-S^{\prime })+2\end{array}$$

which contradicts the corollary. Thus no such subset exists and, by IH, $G^{\prime }$ has as a perfect matching $M^{\prime }$. Then $M=M\cup \{e\}$ is a perfect matching for $M$.

Case 2: Suppose we took a maximal $S$ such that $|S|=\Omega (G-S)$. Let $|S|=k$ such that there are $k$ total odd connected components in $G-S$. Let $C_1,C_2,\dots ,C_k$ be these connected components. Let $U$ be the union of the vertices in the even components (if any).

To construct a perfect matching for $G$,

1. the even components in $G-S$ must have a perfect matching (there are actually none)
2. some vertex in the odd components and $S$ must have a perfect matching
3. the remaining vertices in $S$ need a perfect matching In particular, we can match each distinct vertex in $S$ to a distinct off component $C_i$, and the remaining vertices in each $C_i$ can be perfectly matched amongst themselves.

For point $1$, if $C$ were an even component of $G-S$, then we can pick some vertex $v\in C$ and let $S^{\prime }=S\cup \{v\}$. I claim that $|S^{\prime }|=\Omega (G-S^{\prime })$. So,

$$|S^{\prime }|=|S|+1=\Omega (G-S)+1$$

Since $C-\{v\}$ has an odd number of vertices, when partitioned, at least one connected component must be odd. Thus,

$$\Omega (G-S^{\prime })\ge \Omega (G-S)+1$$

From our global assumption, we know $|S^{\prime }|\ge \Omega (G-S^{\prime })$. Thus,

$$|S^{\prime }|-\Omega (G-S^{\prime })\le (|S|+1)-(\Omega (G-S)+1)=0$$

where $|S|=\Omega (G-S)$ comes from our case premise. In particular, this means that $|S^{\prime }|=\Omega (G-S^{\prime })$. But then this is a contradiction on the maximality of $S$, since $S⊊S^{\prime }$ and $S^{\prime }$ satisfies the equality.

For point $3$, if $C$ is an odd connected component of $G-S$, then for some $v\in C,C-\{v\}$ has a perfect matching. Assume for the sake of contradiction that $C^{\prime }=C-\{v\}$ does not have a perfect matching. By the IH, then $\exists T\subset C^{\prime }$ such that $|T|<\Omega (C^{\prime }-T)$.

By Lemma (Tutte’s Parity of V), $\Omega (C^{\prime }-T)-|T|$ is even, and by Corollary (Tutte Condition),

$$|T|\le \Omega (C^{\prime }-T)-2$$

Let $S^{\prime }=S\cup \{v\}\cup T$. So,

$$|S^{\prime }|=|S|+|T|+1$$

When we remove $\{v\}\cup T$ from $C$, we get some odd components. Indeed, we have $\Omega (C^{\prime }-T)$ total components. So,

$$\Omega (G-S^{\prime })=\Omega (G-S)-1+\Omega (C^{\prime }-T)$$

Where the $1$ compensates for $C^{\prime }$, which is now even. We have that

$$\begin{array}{rl}\Omega (G-S^{\prime })& =\Omega (G-S)-1+\Omega (C^{\prime }-T)\\ & =|S|-1+\Omega (C^{\prime }-T)\\ & \ge |S|-1+|T|+2\\ & =|S|+|T|+1\\ & =|S^{\prime }|\end{array}$$

but here, we assumed $S$ was maximal. But here, $S^{\prime }$ is a larger set that also holds, which is a contradiction on the maximality of $S$.

Now we need to show point $2$. We need to show that there is a perfect matching between the odd connected components of $G-S$ and $S$ itself. In particular, we apply Hall’s Theorem. There is a perfect matching unless there $\exists T\subset S$ such that

$$|N(T)|<|T|$$

Where $|N(T)|$ is the number of all connected components of $G-S$ adjacent to some vertex in $T$. Let $S^{\prime }=S-T$. We have that

$$|S^{\prime }|=|S|-|T|$$

and

$$\Omega (S^{\prime })\ge \Omega (S)-|N(T)|$$

where $T$ “steals” away the connected components of $S$ from $S^{\prime }$. By algebra,

$$\begin{array}{rl}\Omega (S^{\prime })& \ge \Omega (S)-|N(T)|\\ & =|S|-|N(T)|\\ & >|S|-|T|\\ & =|S^{\prime }|\end{array}$$

which is a contradiction of the original assumption of Tutte’s Theorem.

Thus the proof is done.

Peterson’s Theorem

Any bridgeless $3-$regular graph has a perfect matching.

We first prove the following lemma:

Lemma (Peterson: Odd Outbound Edges)

If $C\subseteq V$ is an odd-sized set of vertices, then the number of edges from $C$ to $V\setminus C$ is odd.

Proof: Let $\partial (C)$ be the set of edges with one endpoint in $C$ to another in $V\setminus C$. So,

$$\sum _{v\in C}\mathrm{deg}(v)=3|C|$$

By Handshake Lemma,

$$\sum _{v\in C}\mathrm{deg}(V)=2|E(C)|+|\partial (C)|$$

such that

$$\begin{array}{rl}3|C|& =2|E(C)|+|\partial (C)|\\ |\partial (C)|& =3|C|-2|E(C)|\\ |\partial (C)|& \equiv (3|C|-2|E(C)|)\mathrm{mod}2\\ & \equiv 3|C|\mathrm{mod}2\\ & \equiv |C|\mathrm{mod}2\\ & \equiv 1\mathrm{mod}2\end{array}$$

where as $3|C|$ is odd, $|\partial (C)|$ is odd.

Corollary (Peterson: Minimum Outbound Edges)

For odd $C\subseteq V,|\partial (C)|\ge 3$. In particular, $|\partial (C)|$ must be odd, so it cannot be $2$. But $G$ is bridgeless, so it cannot be $1$. Thus it must be at least $3$.

Peterson’s Theorem Proof:

We can now apply Tutte’s Theorem.

Assume for sake of contradiction that there was no perfect matching. Then $\exists S$ where $|S|<\Omega (G-S)$. Each of the vertices in $S$ to the odd components $C_1,\dots ,C_k$ have degree at most $3$.

For each $C_i$, it must have at least $3$ edges leaving the component. We get a sort of bipartite graph between $S$ and $C_i$. By the Bipartite Handshake Lemma,

$$\begin{array}{rl}3\Omega (G-S)\le \sum _{v\in C_i}\mathrm{deg}(v)& =\sum _{v\in S}\mathrm{deg}(v)\le 3|S|\\ \Omega (G-S)& \le |S|\end{array}$$

which is a contradiction. Therefore there must be a perfect match.

Footnotes

1. See Definition (Odd Connected Components) for $\Omega (G-S)$, the number of connected components with an odd number of vertices. ↩ ↩²