Tutte theorem

Let $G(V,E)$ be any finite graph. $G$ has a complete matching if and only if for all $X\subseteq V(G)$ the inequality $c_{p}(G-X)\leq|X|$ holds, where $c_{p}(H)$ is the number of the components of the $H$ graph with odd number of vertices. This is called the Tutte condition.

Proof.

In a complete matching there is at least one edge between $X$ and the odd components of $G-X$ , and different edges have distinct endvertices. So $c_{p}(G-X)\leq|X|$ . This proves the necessity.

The sufficiency is proved in a few steps indirectly.

1.

It is very easy to see that if $|V(G)|$ is even, then $c_{p}(G-X)\neq|X|-1$ and $c_{p}(G-X)\neq|X|+1$ . This will be used later. And if the Tutte condition holds, applying it to $X=\emptyset$ gives $|V(G)|$ is even.
2.

Now assume there exists a graph satisfying the Tutte condition but without complete matching ,and let $G$ be such a counterexample with the lowest number of vertices. There exist a set $Y\subseteq V(G)$ such that $c_{p}(G-Y)=|Y|$ , examples are the empty set and every vertex. Let $Y_{0}$ be such set with the highest number of vertices.
3.

If $G_{s}$ is an even component in $G-Y_{0}$ , then adding its vertex $t$ to $Y_{0}$ gives $c_{p}(G-Y_{0}-\{t\})\geq|Y_{0}|+1$ , because it creates at least one odd component. But this with the Tutte condition gives $c_{p}(G-Y_{0}-\{t\})=|Y_{0}\cup\{t\}|$ , which contradicts the maximality of $Y_{0}$ . So there are no even components in $G-Y_{0}$ .
4.

Let $G_{p}$ be an odd component of $G-Y_{0}$ , and let $t$ any of its vertices. Assume there is no complete matching in $G_{p}-\{t\}$ . Since $G$ is minimal counterexample, there exits a set $X\subseteq G_{p}-\{t\}$ such that $c_{p}(G_{p}-\{t\}-X)>|X|$ , but because of $(1)$ it is at least $|X|+2$ . Then $c_{p}(G-X-Y_{0}-\{t\})\geq|Y_{0}|-1+|X|+2=|X\cup Y_{0}\cup\{t\}|$ , which contradicts the maximality of $Y_{0}$ . So by removing any vertex from an odd component the remaining part has a complete matching.
5.

Represent each odd components by one vertex, and remove the edges in $Y_{0}$ . From the definition of $Y_{0}$ this is a bipartite graph. If we choose $p$ vertices from the representatives of the odd components, they are together adjacent to at least $p$ vertices in $Y_{0}$ , otherwise we could remove less than $p$ vertices from $Y_{0}$ thus from $V(G)$ , and still get $p$ odd component, which violates the Tutte condition. So there is complete matching in this reduced graph because of Hall’s marriage theorem.
6.

The complete matching in the reduced graph covers $Y_{0}$ and exactly one vertex in each odd component. But there is also a matching in the rest of each odd component covering the rest as proven in $(4)$ , and from $(3)$ there are no even components. Combining these gives a complete matching of $G$ , which is a contradiction.

∎

Title	Tutte theorem
Canonical name	TutteTheorem
Date of creation	2013-03-22 14:06:04
Last modified on	2013-03-22 14:06:04
Owner	scineram (4030)
Last modified by	scineram (4030)
Numerical id	11
Author	scineram (4030)
Entry type	Theorem
Classification	msc 05C70