Let be a graph and a subgraph of . Let the number of odd components in be denoted , and the number of graph vertices of . The condition for every subset of graph vertices is necessary and sufficient for to have a 1-graph factor.
Tutte's Theorem
See also
Graph Factor, Perfect Matching, Petersen's TheoremExplore 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 TheoremCite this as:
Weisstein, Eric W. "Tutte's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TuttesTheorem.html