What Is 1-factorization conjecture

Content on WhatAnswers is provided "as is" for informational purposes. While we strive for accuracy, we make no guarantees. Content is AI-assisted and should not be used as professional advice.

Last updated: April 11, 2026

Quick Answer: The 1-factorization conjecture is a major unsolved problem in graph theory stating that regular graphs with sufficiently high degree are 1-factorable (decomposable into perfect matchings). Csaba, Kühn, Lo, Osthus and Treglown proved a 60-year-old version of Dirac's conjecture in 2019, showing that d-regular graphs on n even vertices with d ≥ 2⌈n/4⌉ − 1 contain 1-factorizations.

Key Facts

A 1-factorization partitions a graph's edges into perfect matchings, equivalent to proper edge-coloring with minimum colors
Dirac proposed the conjecture in the 1950s, stating every regular graph with sufficient degree must be 1-factorable
Csaba, Kühn, Lo, Osthus and Treglown proved the degree-threshold version in 2019 after 60+ years of research
A 1-factor is a perfect matching—a set of edges where every vertex appears exactly once
The conjecture implies that regular graphs with k ≥ n (odd) or k ≥ n-1 (even) vertices are 1-factorable

Overview

The 1-factorization conjecture is one of the most celebrated open problems in combinatorial graph theory. At its core, the conjecture addresses a fundamental question: when can the edges of a regular graph be partitioned into disjoint perfect matchings? A 1-factor is a perfect matching—a subset of edges where every vertex appears exactly once—and a 1-factorization is a decomposition of all edges into such matchings.

Proposed in the 1950s by mathematician Paul Dirac, this conjecture has driven decades of research in combinatorics. The conjecture essentially claims that any regular graph with sufficiently high degree must admit a 1-factorization. In 2019, after more than 60 years of effort, mathematicians Csaba, Kühn, Lo, Osthus, and Treglown proved a major version of the conjecture, marking a watershed moment in the field and validating the problem's fundamental importance.

How It Works

Understanding the 1-factorization conjecture requires grasping several key concepts:

Regular Graphs: A graph is k-regular if every vertex has exactly k edges. For a 1-factorization to exist, the graph must be regular—if vertices have different degrees, perfect matchings cannot partition all edges evenly.
Perfect Matchings: A perfect matching is a set of edges where each vertex appears exactly once. In a graph with n vertices, a perfect matching contains exactly n/2 edges. A 1-factor and a perfect matching are synonymous terms.
Edge Partitioning: A 1-factorization divides all edges of the graph into disjoint perfect matchings. For a k-regular graph on n vertices with kn/2 total edges, exactly k perfect matchings are needed.
Degree Thresholds: The conjecture concerns degree thresholds—the minimum degree d such that every d-regular graph admits a 1-factorization. Dirac conjectured this threshold was approximately n/4 for n-vertex graphs.
Complete Graphs: Complete graphs K_n are studied intensively. The 1-factorization of K_n requires partitioning its n(n-1)/2 edges into perfect matchings, with direct applications to tournament scheduling.

Key Comparisons

Concept	Definition	Relevance to Conjecture
1-Factor	A perfect matching; a spanning subgraph where every vertex has degree 1	The building block of 1-factorization; the conjecture asks when graphs can be fully decomposed into these
k-Regular Graph	A graph where every vertex has exactly k edges	Necessary condition for 1-factorization; irregular graphs cannot be 1-factorable
Hamilton Cycle	A cycle visiting every vertex exactly once	Related problem: decomposing regular graphs into Hamilton cycles, proved alongside 1-factorization conjecture
Edge Coloring	Assigning colors to edges so no two adjacent edges share a color	A k-regular graph's 1-factorization is equivalent to proper edge-coloring with k colors
Perfect Matching	A matching covering all vertices; requires n vertices and n/2 edges	The core unit; 1-factorization = partition into perfect matchings

Why It Matters

Theoretical Significance: The conjecture represents a fundamental question in extremal combinatorics—understanding the structure and decomposition of regular graphs. Proving or disproving it advances core mathematical knowledge about graph properties.
Practical Applications: 1-factorizations have direct applications in tournament scheduling, where players must be paired into non-overlapping rounds. Sports leagues and chess competitions use factorization algorithms for fair scheduling.
Computational Complexity: Algorithms for finding 1-factorizations are important in computational graph theory. Efficient factorization methods enable optimization of large-scale matching problems in logistics and telecommunications.
Mathematical Breakthrough: The 2019 proof by Csaba, Kühn, Lo, Osthus, and Treglown confirmed that the degree threshold d ≥ 2⌈n/4⌉ − 1 suffices for every d-regular n-vertex graph (n even) to be 1-factorable, resolving a 60-year conjecture.

The resolution of Dirac's version of the 1-factorization conjecture exemplifies how patience, collaboration, and sophisticated proof techniques can overcome long-standing mathematical challenges. The conjecture's legacy extends beyond graph theory, influencing research in combinatorial optimization and design theory. Future work may fully resolve the original conjecture for all degree thresholds, further cementing the foundational role of 1-factorization in mathematics.