Abstract
This exposition is concerned with the main theorems of graph-factor theory, Hall’s and Ore’s Theorems in the bipartite case, and in the general case Petersen’s Theorem, the 1-Factor Theorem and thef-Factor Theorem. Some published extensions of these theorems are discussed and are shown to be consequences rather than generalizations of thef-Factor Theorem. The bipartite case is dealt with in Section 2. For the proper presentation of the general case a preliminary theory of “G-triples” and “f-barriers” is needed, and this is set out in the next three Sections. Thef-Factor Theorem is then proved by an argument of T. Gallai in a generalized form. Gallai’s original proof derives the 1-Factor Theorem from Hall’s Theorem. The generalization proceeds analogously from Ore’s Theorem to thef-Factor Theorem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Erdős andT. Gallai, Graphs with prescribed valencies,Mat. Lapok 11 (1960) 264–274. (Hungarian).
T. Gallai, Neuer Beweis eines Tutte’schen Satzes,Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 135–139.
P. Hall, On representatives of subsets,J. London Math. Soc. 10 (1935), 26–30.
M. Las Vergnas, An extension of Tutte’s 1-factor theorem,Discrete Math.,23 (1978), 241–255.
L. Lovász, Subgraphs with prescribed valencies,J. Combinatorial Theory 8 (1970), 391–416.
O. Ore, Studies on directed graphs I, II, III.Ann. Math. 63 (1956), 383–406;64 (1956), 142–153;68 (1958), 526–549.
J. Petersen, Die Theorie der regulären Graphs,Acta Math. 15 (1891), 193–220.
W. T. Tutte, The factorization of linear graphs,J. London Math. Soc. 22 (1947), 107–111.
W. T. Tutte, The factors of graphs,Can. J. Math.,4 (1952), 314–328.
W. T. Tutte, A short proof of the factor theorem for finite graphs,Can. J. Math. 6 (1954), 347–352.
W. T. Tutte, Spanning subgraphs with specified valencies,Discrete Math. 9 (1974), 97–108.
W. T. Tutte, The subgraph problem,Annals of Discrete Math. 3 (1978), 289–295.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Tutte, W.T. Graph factors. Combinatorica 1, 79–97 (1981). https://doi.org/10.1007/BF02579180
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02579180