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 the marriage theorem and is a special case of the Tutte-Berge formula.

Tutte's theorem

A given graph $G=\; left(\; V,\; E\; ight)$ has a perfect matching if and only if for every subset $U$ of $V$ the number of connected components with an odd number of vertices in the subgraph induced by $V\; setminus\; U$ is less than or equal to the cardinality of $U$.

Proof

To prove that $(*)forall\; U\; subseteq\; V,;\; o(G-U)le|U|$ is a necessary condition:

Consider a graph $G$, with a perfect matching. Let $U$ be an arbitrary subset of $V$. Delete $U$. Consider an arbitrary odd component in $G-U,;C$. Since $G$ had a perfect matching, at least one edge in $C$ must be matched to a vertex in $U$. Hence, each odd component has at least one edge matched with a vertex in $U$. Thus $o(G-U)le\; |U|$.

To prove that $(*)$ is sufficient:

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 $u-1$ where $u\; =\; |V|$. 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 since $U$ is complete.

References

* J.A. Bondy and U.S.R. Murty, "Graph Theory with Applications"

See also

* Marriage theorem
* Bipartite matching
* Tutte-Berge formula