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.
Contents |
[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 condition 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
