Tutte theorem


Let G(V,E) be any finite graph. G has a complete matching if and only if for all XV(G) the inequality cp(G-X)|X| holds, where cp(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 cp(G-X)|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 cp(G-X)|X|-1 and cp(G-X)|X|+1. This will be used later. And if the Tutte condition holds, applying it to X= 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 YV(G) such that cp(G-Y)=|Y|, examples are the empty setMathworldPlanetmath and every vertex. Let Y0 be such set with the highest number of vertices.

  3. 3.

    If Gs is an even component in G-Y0, then adding its vertex t to Y0 gives cp(G-Y0-{t})|Y0|+1, because it creates at least one odd component. But this with the Tutte condition gives cp(G-Y0-{t})=|Y0{t}|, which contradicts the maximality of Y0. So there are no even components in G-Y0.

  4. 4.

    Let Gp be an odd component of G-Y0, and let t any of its vertices. Assume there is no complete matching in Gp-{t}. Since G is minimal counterexample, there exits a set XGp-{t} such that cp(Gp-{t}-X)>|X|, but because of (1) it is at least |X|+2. Then cp(G-X-Y0-{t})|Y0|-1+|X|+2=|XY0{t}|, which contradicts the maximality of Y0. 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 Y0. From the definition of Y0 this is a bipartite graphMathworldPlanetmath. If we choose p vertices from the representatives of the odd components, they are together adjacent to at least p vertices in Y0, otherwise we could remove less than p vertices from Y0 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 theoremMathworldPlanetmath.

  6. 6.

    The complete matching in the reduced graph covers Y0 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 contradictionMathworldPlanetmathPlanetmath.

Title Tutte theoremMathworldPlanetmath
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 TheoremMathworldPlanetmath
Classification msc 05C70