1-Factorization Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite simple undirected graph is $k$-regular if each vertex has degree $k$. A 1-factor is a perfect matching: a set of pairwise vertex-disjoint edges meeting every vertex once. A 1-factorization is a partition of the edge set into perfect matchings. Define $b(n)=n$ for odd $n$ and $b(n)=n-1$ for even $n$.

Statement recorded in the supplied source.

For every $n\in\mathbb N$, every integer $k\ge b(n)$, and every $k$-regular simple graph $G$ on $2n$ vertices, must $G$ have a 1-factorization into $k$ perfect matchings? Equivalently, is the threshold $k\ge2\lceil n/2\rceil-1$ sufficient for every order $2n$? [S1][S2] The cited theorem proves this assertion for all sufficiently large $n$; the catalogue question here retains its stated quantifier over every $n$.

Short English statement

Does every regular graph on twice n vertices decompose into perfect matchings when its degree is at least n, or at least n minus one when n is even?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1393 (GRAPH-006). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures, Memoirs of the American Mathematical Society 244 (2016); arXiv:1401.4159v2, Section 1.1, Theorem 1.1.1. https://arxiv.org/abs/1401.4159v2.