Tutte's 1-factor theorem

GPTKB entity

Statements (15)
Predicate Object
gptkbp:instanceOf gptkb:mathematical_concept
gptkbp:alsoKnownAs Tutte's matching theorem
gptkbp:appliesTo finite undirected graphs
gptkbp:field graph theory
gptkbp:generalizes gptkb:Petersen's_theorem
https://www.w3.org/2000/01/rdf-schema#label Tutte's 1-factor theorem
gptkbp:influenced matching theory
gptkbp:namedAfter gptkb:W._T._Tutte
gptkbp:publicationYear 1947
gptkbp:publishedIn On the factorization of linear graphs, Journal of the London Mathematical Society
gptkbp:relatedConcept gptkb:matching_(graph_theory)
perfect matching
gptkbp:state A finite graph has a 1-factor if and only if for every subset S of its vertices, the number of odd components of the subgraph induced by the remaining vertices is at most |S|.
gptkbp:bfsParent gptkb:Tutte's_theorem
gptkbp:bfsLayer 7