Set of Tutte

This article deals with the sentence after William Thomas Tutte. For the Hamilton cycle problem see Tutte's theorem (Hamilton cycle problem) .

The Tutte theorem (after William Thomas Tutte ) is a mathematical theorem from graph theory . It reads:

A graph G = ( V , E ) has a perfect matching if and only if for every subset S of the node set V the number of connected components of odd cardinality of G - S is at most equal to | S |, the number of nodes in S 's.

G - S denotes the graph that arises when the nodes of S and their incident edges are deleted from G. If q ( G ) denotes the number of connected components with an odd number of nodes in a graph G = ( V , E ), the second condition can be written as | S | ≥ q ( G - S ) for all subsets S of  V .

literature

• Lutz Volkmann: Foundations of the graph theory . Springer, (Vienna) 1996, ISBN 3-211-82774-9 , p. 137, sentence 7.2

Web links

• Eric W. Weisstein : Tutte's 1-factor set . In: MathWorld (English). (English)
• Lutz Volkmann: Graphs on all corners and edges . (PDF; 3.7 MB) 2006, p. 114, sentence 7.1 (not published as a book)