Tutte theorem

From Wikipedia, the free encyclopedia

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte-Berge formula.

Contents 1 Tutte's theorem 2 Proof 3 References 4 See also

[edit] Tutte's theorem

A given graph has a perfect matching if and only if for every subset U of V the number of connected components with an odd number of vertices in the subgraph induced by is less than or equal to the cardinality of U.

[edit] Proof

To prove that is a necessary condition:

Consider a graph G, with a perfect matching. Let U be an arbitrary subset of V. Delete U. Consider an arbitrary odd component in . Since G had a perfect matching, at least one edge in C must be matched to a vertex in U. Hence, each odd component has at least one edge matched with a vertex in U. Thus .

To prove that ( * ) is sufficient:

Let G be an arbitrary graph satisfying ( * ). Consider the expansion of G to G * , a maximally imperfect graph, in the sense that G is a spanning subgraph of G * , but adding an edge to G * will result in a perfect matching. We observe that G * also satisfies condition ( * ) since G * is G with additional edges. Let U be the set of vertices of degree ν − 1 where ν = | V | . By deleting U, we obtain a disjoint union of complete graphs (each component is a complete graph). A perfect matching may now be defined by matching each even component independently, and matching one vertex of an odd component C to a vertex in U and the remaining vertices in C amongst themselves (since an even number of them remain this is possible). The remaining vertices in U may be matched similarly since U is complete.

[edit] References

• J.A. Bondy and U.S.R. Murty, Graph Theory with Applications

[edit] See also

• Marriage theorem
• Bipartite matching
• Tutte-Berge formula