Perfect 1-Factorization Conjecture

Perfect One-Factorizations of Complete Graphs

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A one-factor is a perfect matching. A one-factorization of $K_{2n}$ partitions its edges into $2n-1$ perfect matchings. It is perfect if the union of any two different matching classes is one Hamiltonian cycle, rather than a disjoint union of shorter even cycles. The conjecture quantifies over all $n\geq2$. [S1] [S2]

Statement recorded in the supplied source.

Does every complete graph on an even number of vertices admit a perfect 1-factorization? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Establish a perfect 1-factorization of every even complete graph. [S1]

Short English statement

Can every even-order complete graph be decomposed into perfect matchings so that any two matchings together form one spanning cycle?

Research attempt

Status: UNRESOLVED. We derive the standard cyclic perfect one-factorization for $K_{p+1}$ with $p$ an odd prime, prove its Hamiltonian property, and give an explicit composite-order failure of the same formula. This infinite special family does not cover every even order.

Source check and target distinction.

Cheng--Sgueglia [S2], consulted 1 October 2026, proves that a one-factorization can have a subfamily of $(1-o(1))n$ matchings whose pairs are Hamiltonian. Its title's asymptotic wording does not assert that every one of the $n-1$ factors participates in such a perfect family. We keep the exact target unchanged. The attack here is algebraic: construct factors by reflections and analyze the components of their pairwise unions.

A one-factorization for every odd modulus.

Let $q\ge3$ be odd and take vertex set $\mathbb Z/q\mathbb Z\cup\{\infty\}$. For each $a\in\mathbb Z/q\mathbb Z$ let \[ F_a=\{\{\infty,a\}\}\cup \{\{x,2a-x\}:x\ne a\}. \] The second collection is a set of unordered pairs, so listing both endpoints does not create repeated edges. The map $x\mapsto2a-x$ is an involution whose only fixed point is $a$, because two is invertible modulo odd $q$. Its remaining vertices form $(q-1)/2$ disjoint pairs. Together with $\{\infty,a\}$ they give a perfect matching.

Every edge involving infinity occurs exactly once. A finite edge $\{x,y\}$ with $x\ne y$ occurs precisely in the factor indexed by $a=(x+y)/2$. Thus the $q$ matchings partition all edges of $K_{q+1}$. This part of the construction needs only oddness, not primality.

Why prime modulus makes every pair Hamiltonian.

Fix distinct $a,b$ and let $q=p$ be prime. The graph $F_a\cup F_b$ is a simple two-regular spanning graph, hence a disjoint union of cycles; factors share no edge. If it is not connected, some component $C$ avoids infinity. It then also avoids $a$ and $b$, because their respective matching edges lead to infinity.

For every $x\in C$, both reflections $r_a(x)=2a-x$ and $r_b(x)=2b-x$ belong to $C$. Their composition is translation by $2(b-a)$ or its negative, depending on order. This translation is nonzero in $\mathbb F_p$ and has one orbit, the whole field. Closure of a nonempty $C$ under the composition therefore forces $C=\mathbb F_p$. That contradicts $a\notin C$. Every component must consequently contain infinity, so there is just one component, a Hamiltonian cycle.

The proof also applies for an odd composite modulus to a particular pair whenever $\gcd(b-a,q)=1$. It is the transitivity of translation, not a generic appeal to symmetry, that supplies connectedness.

The composite obstruction is real.

For $q=9$, take $a=0$ and $b=3$. The component containing infinity is the four-cycle \[ \infty,0,6,3,\infty. \] Indeed $\infty0$ and $63$ are in $F_0$, while $06$ and $3\infty$ are in $F_3$. The other six vertices form another component. Thus this one-factorization of $K_{10}$ is not perfect. This is not a counterexample to the existence conjecture, which permits completely different factors. It rules out the unqualified extension of the prime proof to every odd modulus.

For a composite odd $q$, choose a nonzero difference sharing a proper divisor with $q$. The translation orbits split into residue classes, and the argument forcing a single component is no longer available. Changing only the names of the vertices or factors preserves component lengths, so relabeling the failed construction cannot repair it.

Executed checks and certificate format.

The audit script constructed all factors for $q=3,5,7,9,11,13,17$, verified that each is a perfect matching, checked that their edge sets partition $K_{q+1}$, and counted components for every pair. It found no disconnected pair at the listed prime moduli. At $q=9$ it found nine bad pairs, including $(0,3)$ with a four-vertex component containing infinity. These exact set and graph traversals are recorded in root/checks.py and root/checks_results.json in the local audit.

For any proposed perfect one-factorization, verifying the target is finite and direct: check the edge partition and traverse every two-factor union. Finding a factorization is the difficult part. A family of many pairwise Hamiltonian factors does not automatically extend by one more factor: the unused edges must support a perfect matching satisfying a connectedness condition against every already chosen factor simultaneously.

Remaining gap.

The unresolved task is construction at every even order beyond the prime-successor family, without retaining any non-Hamiltonian pair. The precise gap in this approach is replacing the transitive translation argument when the modulus has nonunits. Local switches in a pair of factors can merge its cycles but can also damage the unions with other factors; no invariant guaranteeing simultaneous improvement is proved here. The result is a checked classical-family derivation and obstruction analysis, with no claimed new solution.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1394 (GRAPH-007), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Y. Cheng and A. Sgueglia, The perfect 1-factorisation conjecture holds asymptotically, arXiv:2607.09459 $2026$. https://arxiv.org/abs/2607.09459. Bibliographic information from the supplied record.