Tutte theorem

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs.^{[clarification needed]} It is a special case of the Tutte–Berge formula.

Tutte's theorem

A graph, $G = (V, E)$ , has a perfect matching if and only if for every subset $U$ of $V$ , the subgraph induced by $V - U$ has at most $| U |$ connected components with an odd number of vertices.^[1]

Proofs

Direct proof

First we write the condition:

(*)\qquad \forall U\subseteq V,\quad o(G-U)\leq |U|

where $o(X)$ denotes the number of odd components of the subgraph induced by $X$ .

Necessity of (∗): Consider a graph $G$ , with a perfect matching. Let $U$ be an arbitrary subset of $V$ . Delete $U$ . Let $C$ be an arbitrary odd component in $G - U$ . Since $G$ had a perfect matching, at least one vertex in $C$ must be matched to a vertex in $U$ . Hence, each odd component has at least one vertex matched with a vertex in $U$ . Since each vertex in $U$ can be in this relation with at most one connected component (because of it being matched at most once in a perfect matching), $o (G - U) \leq | U |$ .^[2]

Sufficiency of (∗): Let $G$ be an arbitrary graph with no perfect matching. We will find a bad set of vertices $S$ , that is, a subset of $V$ such that $| S | < o (G - S)$ . We can suppose that $G$ is edge-maximal, i.e., $G + e$ has a perfect matching for every edge $e$ not present in $G$ already. Indeed, if we find a bad set $S$ in edge-maximal graph $G$ , then $S$ is also a bad set in every spanning subgraph of $G$ , as every odd component of $G - S$ will be split into possibly more components at least one of which will again be odd.

We define $S$ to be the set of vertices with degree $| V | - 1$ . First we consider the case where all components of $G - S$ are complete graphs. Then $S$ has to be a bad set, since if $o (G - S) \leq | S |$ , then we could find a perfect matching by matching one vertex from every odd component with a vertex from $S$ and pairing up all other vertices (this will work unless $| V |$ is odd, but then $\emptyset$ is bad).

Now suppose that $K$ is a component of $G - S$ and $x, y \in K$ are vertices such that $xy \notin E$ . Let $x, a, b \in K$ be the first vertices on a shortest $x, y$ -path in $K$ . This ensures that $xa, ab \in E$ and $xb \notin E$ . Since $a \notin S$ , there exists a vertex $c$ such that $ac \notin E$ . From the edge-maximality of $G$ , we define $M 1$ as a perfect matching in $G + xb$ and $M 2$ as a perfect matching in $G + ac$ . Observe that surely $xb \in M 1$ and $ac \in M 2$ .

Let $P$ be the maximal path in $G$ that starts from $c$ with an edge from $M 1$ and whose edges alternate between $M 1$ and $M 2$ . How can $P$ end? Unless we are arrive at 'special' vertex such as $x, a$ or $b$ , we can always continue: $c$ is $M 2$ -matched by $ca$ , so the first edge of $P$ is not in $M 2$ , therefore the second vertex is $M 2$ -matched by a different vertex and we continue in this manner.

Let $v$ denote the last vertex of $P$ . If the last edge of $P$ is in $M 1$ , then $v$ has to be $a$ , since otherwise we could continue with an edge from $M 2$ (even to arrive at $x$ or $b$ ). In this case we define $C := P + ac$ . If the last edge of $P$ is in $M 2$ , then surely $v \in {x, b$ } for analogous reason and we define $C := P + va + ac$ .

Now $C$ is a cycle in $G + ac$ of even length with every other edge in $M 2$ . We can now define $M := M 2 Δ C$ (where $Δ$ is symmetric difference) and we obtain a matching in $G$ , a contradiction.

Derivation from the Tutte-Berge formula

The Tutte–Berge formula says that the size of a maximum matching of a graph $G=(V,E)$ equals ${\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)$

Tutte's condition is that, for every $U\subseteq V$ , ${\text{odd}}(G-U)\leq |U|$ . Equivalently, the expression inside the minimum is at least $|V|$ . Equivalently, the entire expression is at least $|V|/2$ .

So, Tutte's condition holds iff the graph has a matching of size at least $|V|/2$ , iff the graph has a perfect matching.

Notes

^ Lovász & Plummer (1986), p. 84; Bondy & Murty (1976), Theorem 5.4, p. 76.
^ Bondy & Murty (1976), pp. 76–78.

References

Bondy, J. A.; Murty, U. S. R. (1976). Graph theory with applications. New York: American Elsevier Pub. Co. ISBN 0-444-19451-7. {{cite book}}: Invalid |ref=harv (help)
Lovász, László; Plummer, M. D. (1986). Matching theory. Amsterdam: North-Holland. ISBN 0-444-87916-1. {{cite book}}: Invalid |ref=harv (help)

[1] Lovász & Plummer (1986), p. 84; Bondy & Murty (1976), Theorem 5.4, p. 76.

[bm-proof-2] Bondy & Murty (1976), pp. 76–78.

[1]

[2]