Content deleted Content added
Added unsolved mathematics card (as this page is listed on that one) |
m custom spacing in math formulas (via WP:JWB) |
||
Line 84:
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: [[2-factor theorem|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 [[connectivity (graph theory)|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 [[counterexample]]s include disjoint unions of odd cycles, or of copies of ''K''<sub>2''k''
The [[Oberwolfach problem]] concerns the existence of 2-factorizations of complete graphs into [[graph isomorphism|isomorphic]] subgraphs. It asks for which subgraphs this is possible. This is known when the subgraph is connected (in which case it is a [[Hamiltonian cycle]] and this special case is the problem of [[Hamiltonian decomposition]]) but the general case remains [[open problem|open]].
| |||