Tutte theorem

Not to be confused with Tutte homotopy theorem or Tutte's spring 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 the marriage theorem and 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.

Proof

First we write the condition:

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

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) ≤ |U|.

Sufficiency of (∗): Let G be an arbitrary graph satisfying (∗). Consider the expansion of G to G∗, a maximally imperfect graph, in the sense that G is a spanning subgraph of G∗, but adding an edge to G∗ will result in a perfect matching. We observe that G∗ also satisfies condition (∗) since G∗ is G with additional edges. Let U be the set of vertices of degree |V| − 1. By deleting U, we obtain a disjoint union of complete graphs (each component is a complete graph). A perfect matching may now be defined by matching each even component independently, and matching one vertex of an odd component C to a vertex in U and the remaining vertices in C amongst themselves (since an even number of them remain this is possible). The remaining vertices in U may be matched similarly, as U is complete.

This proof is not complete. Deleting U may yield a disjoint union of complete graphs, but the case where it does not is the more interesting and difficult part of the proof.

See also

• Bipartite matching
• Hall's theorem
• Petersen's theorem

References

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