- Tutte theorem
In the
mathematical discipline ofgraph theory the Tutte theorem, named afterWilliam Thomas Tutte , is a characterization of graphs withperfect matching s. It is a generalization of themarriage theorem and is a special case of theTutte-Berge formula .Tutte's theorem
A given graph G= left( V, E ight) 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 thesubgraph induced by V setminus U is less than or equal to thecardinality of U.Proof
To prove that forall U subseteq V,; o(G-U)le|U| 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 G-U,;C . 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 o(G-U)le |U|.
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 u-1 where u = |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.
References
* J.A. Bondy and U.S.R. Murty, "Graph Theory with Applications"
See also
*
Marriage theorem
*Bipartite matching
*Tutte-Berge formula
Wikimedia Foundation. 2010.