Graph factorization

One method for constructing a 1-factorization of a complete graph on an even number of vertices involves placing all but one of the vertices in a regular polygon, with the remaining vertex at the center.

With this arrangement of vertices, one way of constructing a 1-factor of the graph is to choose an edge e from the center to a single polygon vertex together with all possible edges that lie on lines perpendicular to e. The 1-factors that can be constructed in this way form a 1-factorization of the graph.

In 1964, Anton Kotzig conjectured that every complete graph K2n where n ≥ 2 has a perfect 1-factorization.

[7] This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of K2k +1.

The Oberwolfach problem concerns the existence of 2-factorizations of complete graphs into isomorphic subgraphs.

1-factorization of the Desargues graph : each color class is a 1-factor .
The Petersen graph can be partitioned into a 1-factor (red) and a 2-factor (blue). However, the graph is not 1-factorable .
1-factorization of K 8 in which each 1-factor consists of an edge from the center to a vertex of a heptagon together with all possible perpendicular edges