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}(GX)\le 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 $GX$, and different edges have distinct endvertices. So ${c}_{p}(GX)\le 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}(GX)\ne X1$ and ${c}_{p}(GX)\ne X+1$. This will be used later. And if the Tutte condition holds, applying it to $X=\mathrm{\varnothing}$ 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}(GY)=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\})\ge {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}(GX{Y}_{0}\{t\})\ge {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  20130322 14:06:04 
Last modified on  20130322 14:06:04 
Owner  scineram (4030) 
Last modified by  scineram (4030) 
Numerical id  11 
Author  scineram (4030) 
Entry type  Theorem^{} 
Classification  msc 05C70 