Content deleted Content added
→2-factorization: The previous version stated that: "If a graph is 2-factorable, then it has to be 2k-regular for some integer k." This is directly contradicted by the Petersen graph, which is 3-regular and has a 2-factor. |
Undid revision 971246833 by 184.161.107.105 (talk) "is 2-factorable" means "can be partitioned into two perfect matchings", and does not mean "has a 2-factor" |
||
Line 80:
==2-factorization==
If a graph is 2-factorable, then it has to be 2''k''-regular for some integer ''k''. [[Julius Petersen]] showed in 1891 that this necessary condition is also sufficient: any 2''k''-regular graph is 2-factorable.<ref>{{harvtxt|Petersen|1891}}, §9, p. 200. {{harvtxt|Harary|1969}}, Theorem 9.9, p. 90. See {{harvtxt|Diestel|2005}}, Corollary 2.1.5, p. 39 for a proof.</ref>
If a connected graph is 2''k''-regular and has an even number of edges it may also be ''k''-factored, by choosing each of the two factors to be an alternating subset of the edges of an [[Euler tour]].<ref>{{harvtxt|Petersen|1891}}, §6, p. 198.</ref> This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of ''K''<sub>2''k''+1</sub>.
| |||