Math Conjectures

Perfect One-Factorization Conjecture

OPENMajorConjectureProposed 1964 · Standard version

Canonical statement

For every integer n≥2n\geq2, the edge set of the complete graph K2nK_{2n} can be partitioned into perfect matchings M1,…,M2n−1M_1,\ldots,M_{2n-1} such that Mi∪MjM_i\cup M_j is a Hamiltonian cycle whenever i≠ji\ne j. A perfect matching is a set of pairwise disjoint edges meeting every vertex exactly once, and a Hamiltonian cycle is a cycle containing every vertex.
View source LaTeX
For every integer \(n\geq2\), the edge set of the
complete graph \(K_{2n}\) can be partitioned into perfect matchings
\(M_1,\ldots,M_{2n-1}\) such that \(M_i\cup M_j\) is a Hamiltonian cycle
whenever \(i\ne j\). A perfect matching is a set of pairwise disjoint
edges meeting every vertex exactly once, and a Hamiltonian cycle is a
cycle containing every vertex.
GRAPH-024:[Kotzig1964P1F][Seah1991P1F][ChengSgueglia2026P1F]
Graph theoryCombinatorics

Notes

Perfect one-factorizations are known for several infinite families and many individual orders. An asymptotic result shows that almost all factors can have the required pairwise property, but an exact construction for every even order remains unknown.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.