# 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