Tutte theorem
Let be any finite graph. has a complete matching if and only if for all the inequality holds, where is the number of the components of the graph with odd number of vertices. This is called the Tutte condition.
Proof.
In a complete matching there is at least one edge between and the odd components of , and different edges have distinct endvertices. So . This proves the necessity.
The sufficiency is proved in a few steps indirectly.
-
1.
It is very easy to see that if is even, then and . This will be used later. And if the Tutte condition holds, applying it to gives is even.
-
2.
Now assume there exists a graph satisfying the Tutte condition but without complete matching ,and let be such a counterexample with the lowest number of vertices. There exist a set such that , examples are the empty set and every vertex. Let be such set with the highest number of vertices.
-
3.
If is an even component in , then adding its vertex to gives , because it creates at least one odd component. But this with the Tutte condition gives , which contradicts the maximality of . So there are no even components in .
-
4.
Let be an odd component of , and let any of its vertices. Assume there is no complete matching in . Since is minimal counterexample, there exits a set such that , but because of it is at least . Then , which contradicts the maximality of . 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 . From the definition of this is a bipartite graph. If we choose vertices from the representatives of the odd components, they are together adjacent to at least vertices in , otherwise we could remove less than vertices from thus from , and still get 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 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 , and from there are no even components. Combining these gives a complete matching of , 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 |