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. 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. 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. 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. 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. 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. 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 TutteTheorem 2013-03-22 14:06:04 2013-03-22 14:06:04 scineram (4030) scineram (4030) 11 scineram (4030) Theorem msc 05C70