Revision as of 16:08, 10 September 2015 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,660 edits Undid revision 680372416 by DerPhimor (talk) you're confusing "has a 1-factor" (=perfect matching) with "has a 1-factorization" (=partition into perfect matchings) ← Previous edit		Revision as of 11:55, 7 November 2016 edit undo 141.250.40.232 (talk) →1-factorization Next edit →
Line 7: ==1-factorization== If a graph is 1-factorable, then it ~~has to~~can be a [[regular graph]]. However, not all regular graphs are 1-factorable. A ''k''-regular graph is 1-factorable if it has [[chromatic index]] ''k''; examples of such graphs include: * Any regular [[bipartite graph]].<ref>{{harvtxt\|Harary\|1969}}, Theorem 9.2, p. 85. {{harvtxt\|Diestel\|2005}}, Corollary 2.1.3, p. 37.</ref> [[Hall's marriage theorem]] can be used to show that a ''k''-regular bipartite graph contains a perfect matching. One can then remove the perfect matching to obtain a (''k'' − 1)-regular bipartite graph, and apply the same reasoning repeatedly. * Any [[complete graph]] with an even number of nodes (see [[#Complete graphs\|below]]).<ref>{{harvtxt\|Harary\|1969}}, Theorem 9.1, p. 85.</ref>

Graph factorization: Difference between revisions