TOPICS
Search

Tutte's Theorem


Let G be a graph and S a subgraph of G. Let the number of odd components in G-S be denoted S^', and |S| the number of graph vertices of S. The condition |S|>=S^' for every subset of graph vertices is necessary and sufficient for G to have a 1-graph factor.


See also

Graph Factor, Perfect Matching, Petersen's Theorem

Explore with Wolfram|Alpha

References

Andersen, L. D. "Factorizations of Graphs." §VII.5 in CRC Handbook of Combinatorial Designs, 2nd ed. Boca Raton, FL: CRC Press, pp. 740-755, 2007.Honsberger, R. "Lovász' Proof of a Theorem of Tutte." Ch. 14 in Mathematical Gems II. Washington, DC: Math. Assoc. Amer., pp. 147-157, 1976.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, p. 344, 2003.Tutte, W. T. "The Factorization of Linear Graphs." J. London Math. Soc. 22, 107-111, 1947.Wallis, W. D. One-Factorizations. Dordrecht, Netherlands: Kluwer, 1997.

Referenced on Wolfram|Alpha

Tutte's Theorem

Cite this as:

Weisstein, Eric W. "Tutte's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TuttesTheorem.html

Subject classifications