WorksMathematics
On Win's Conjecture for Edge-Disjoint Perfect Matchings
Abstract
In 1982, Win conjectured that, for every even integer and every integer , any graph of order satisfying for every pair of nonadjacent vertices contains pairwise edge-disjoint perfect matchings. In this paper, we prove a stronger result for all sufficiently large even . More precisely, we show that under the same degree-sum condition, contains pairwise edge-disjoint Hamilton cycles, together with an additional perfect matching when is odd, all pairwise edge-disjoint. Consequently, we confirm Win's conjecture for all sufficiently large even , with a threshold independent of .
Introduction
Graph decomposition problems form a central and active area of research in graph theory. A decomposition of a graph is a collection of pairwise edge-disjoint subgraphs whose edge sets partition . If all these subgraphs are isomorphic to a prescribed graph , then the decomposition is called an -decomposition. The study of graph decompositions has a long history. A classical result of Walecki [1] shows that the complete graph can be decomposed into Hamilton cycles, while can be decomposed into Hamilton cycles and a perfect matching.
More recently, Csaba, Kühn, Lo, Osthus and Treglown [3] resolved the 1-factorization and Hamilton decomposition conjectures for sufficiently large graphs. In particular, they established the following result.
Theorem 1.1 (Csaba et al. [3]). There exists an integer such that every -regular graph on vertices with admits a decomposition into Hamilton cycles and, if is odd, one perfect matching.
Another important result is the Hamilton decomposition theorem of Kühn and Osthus [8] for robust expanders. For and , the robust -neighborhood of is defined by . A graph of order is called a robust -expander if for every with . Kühn and Osthus established the following result.
Theorem 1.2 (Kühn and Osthus [8]). For every , there exist constants and such that, for every , there exists an integer with the following property. Every even-regular robust -expander on vertices with admits a Hamilton decomposition.
This theorem is a key ingredient in the proof of Theorem 1.1. Indeed, for every fixed , every graph with is a robust -expander. Consequently, Theorem 1.2 implies the asymptotic version of Theorem 1.1.
A natural relaxation of a graph decomposition problem is to require only that the prescribed subgraphs are pairwise edge-disjoint, without insisting that they cover all edges of the host graph. A fundamental problem in this direction is to determine sufficient conditions for the existence of many pairwise edge-disjoint perfect matchings. For a graph , let denote the minimum of over all pairs of distinct nonadjacent vertices , with . Win [14] proposed the following conjecture for edge-disjoint perfect matchings.
Conjecture 1.3 (Win [14]). Let be even and . If an -vertex graph satisfies , then contains pairwise edge-disjoint perfect matchings.
The cases follow from Ore’s theorem [12], while Win [14] established the case . For every fixed even , the Hamilton cycle packing theorem of Faudree, Rousseau and Schelp [5] also implies Conjecture 1.3 for sufficiently large . A substantial advance was made by Lu and Ning [11], who confirmed the conjecture for all when is sufficiently large. We state their result explicitly.
Theorem 1.4 (Lu and Ning [11]). There exists an integer such that, whenever is even and , every -vertex graph satisfying contains pairwise edge-disjoint perfect matchings.
In this paper, we confirm Conjecture 1.3 for all sufficiently large even independent of . In fact, we establish the following stronger result, which guarantees edge-disjoint Hamilton cycles together with, when necessary, one additional perfect matching.
Theorem 1.5. There exists an integer such that, whenever is even, , and is an -vertex simple graph satisfying , the following assertions hold. If is even, then contains pairwise edge-disjoint Hamilton cycles. If is odd, then contains pairwise edge-disjoint Hamilton cycles together with a perfect matching edge-disjoint from all of them.
Since every Hamilton cycle in an even-order graph can be decomposed into two perfect matchings, Theorem 1.5 immediately yields the following confirmation of Conjecture 1.3 for large .
Corollary 1.6. There exists an integer such that, for every even and every integer , each -vertex graph with contains pairwise edge-disjoint perfect matchings.
Preliminaries
Notation
All graphs are finite, simple and undirected. For a vertex of , let and denote its neighborhood and degree, respectively. We write for the closed neighborhood of . The minimum and maximum degrees are and . A vertex cut, or simply a cut, of is a set such that is disconnected or has at most one vertex, the vertex connectivity is the minimum size of such a set. For any , let . In particular, edges with both endpoints in are counted twice. A -factor is a spanning -regular subgraph.
Useful tools
We begin by recalling several results that will be used in our proofs.
Lemma 2.1 (Egawa [4]). Let and . If an -vertex graph satisfies and , then contains pairwise edge-disjoint Hamilton cycles.
Lemma 2.2 (Li [10]). Let and let be a -connected graph on vertex. If every pair of vertices at distance two satisfies , then contains pairwise edge-disjoint Hamilton cycles.
Lemma 2.3 (Bondy and Chvátal [2]). Let be an -vertex graph, and let be nonadjacent vertices of . If , then is Hamiltonian if and only if is Hamiltonian.
Lemma 2.4 (Lu and Ning [11]). Let with even. If is an -vertex graph satisfying , then contains a -factor.
For a function , an -factor of is a spanning subgraph such that for every . We also use Tutte’s -factor theorem [13]. For a graph and , write .
Lemma 2.5 (Tutte [13]). A graph has an -factor if and only if, for all disjoint sets , , where count the components of for which is odd.
We first establish a connectivity property. The first assertion of the following proposition was also proved by Lai and Yan [9].
Proposition 2.6. Let , and let be an -vertex graph satisfying . Then . Moreover, if and , there is an edge such that .
Proof. Suppose that is a vertex cut of . Let be two distinct components of . For any and , we have
Thus , giving .
If and . Then equality in (2) holds throughout, so consists of exactly two cliques and , and every vertex of is adjacent to every vertex of .
Assume . Choose and , and let . For any with , if , then is connected by the edge . Otherwise, and , since . As all edges between these two nonempty sets are present, is connected. Hence .
Lemma 2.7 (Chernoff bound [6]). Let be a sum of independent Bernoulli random variables with . Then the following holds:
For every , .
For every , .
Proof of main Theorem
Small case.
The next lemma deals with the range of small .
Lemma 3.1. Let be even, , and . Every -vertex graph with satisfies the conclusion of Theorem 1.5.
Proof. For , add a universal vertex to . The resulting -vertex graph meets Ore’s condition and has a Hamilton cycle; deleting the new vertex yields a Hamilton path in , which contains a perfect matching since is even. For , Ore’s theorem supplies a Hamilton cycle directly.
Now suppose and let . We first show that if is -connected then it contains pairwise edge-disjoint Hamilton cycles.
Starting from , we can add an edge whenever . This process terminates with a sequence such that every pair of nonadjacent vertices in satisfies .
We claim that adding edge preserves the existence of edge-disjoint Hamilton cycles. Indeed, suppose there are edge-disjoint Hamilton cycles in , and at most one of its cycles uses , say . Let . Then is Hamiltonian and , by Lemma 2.3, has a Hamilton cycle , combining with , there are edge-disjoint Hamilton cycles in .
It remains to find edge-disjoint Hamilton cycles in . If , then Lemma 2.1 applies, since . Otherwise, choose with , and let . Each satisfies .
Now let be any vertex with . If is nonadjacent to some , then , where the last inequality follows from and . This contradicts the construction of . Thus is adjacent to every vertex of , and hence . Since , every pair of vertices at distance two has at least one endpoint of degree at least . Consequently, for every pair at distance two. As is -connected, Lemma 2.2 yields edge-disjoint Hamilton cycles in , and hence also in .
By Proposition 2.6, . If , then is -connected, and the preceding argument gives edge-disjoint Hamilton cycles in . Assume that , then . If , by Proposition 2.6, there exist an edge such that is -connected, otherwise, set . Applying the preceding argument again, we obtain edge-disjoint Hamilton cycles in . At most one of these cycles uses , if added. Deleting from that cycle if necessary (or any edge otherwise) yields a Hamilton path in edge-disjoint from the remaining Hamilton cycles. Since is even, this path contains a perfect matching, as required.
Extension to regular factors
Proposition 3.2. Let be an -vertex graph satisfying . For any subsets with , we have
Proof. The inequality is trivial if either or is empty. Thus we may assume . Let be the bipartite graph with vertex classes given by disjoint copies of and , in which there is an edge between and if and only if and . Consequently, for every , . Then, we have
Hence . Since , the claim follows.
Lemma 3.3. For every , there exist and such that the following holds. Let , with even, and let be an -vertex graph satisfying . Then every with is contained in a -factor of .
Proof. Choose constants
Let with , and put . We claim that . By Proposition 2.6, . Suppose that is disconnected for some with . For every component of and every , we have , which implies . Let be two distinct components of . Since , every edge of between and must belong to . If all edges between and were present in , then for any , a contradiction. Thus there exist and such that . Consequently, , contrary to the Ore condition. Hence .
Define for every . Then and is even. Let be disjoint subsets of , we have
Suppose first that . Since , is connected, so . By , we have . Thus, the left-hand side of (3) is at least . Since is even and
implies that . Now suppose that .
Let . If , then . Otherwise, . Applying Proposition 3.2 and using , we obtain is greater than
By (2) and . Thus, in all cases, . Consequently, by (3), . Thus Lemma 2.5 holds for all disjoint sets and has an -factor. Thus, has a -factor containing all the edge of .
Construction of robust expanders
Lemma 3.4. For every and , there exist and such that the following holds. Let , , and let be an -vertex graph satisfying . Then, for every matching in , there exists a spanning robust -expander with .
Proof. Choose constants such that . Select each edge of independently with probability , and let be the resulting spanning graph. For every , . By Lemma 2.7,
Let satisfy and . Since and , by Proposition 3.2, and noting that removing a matching deletes at most edges, we obtain
at least distinct edges are counted by . Let be the number of distinct edges counted by that are selected into . Since each edge is counted at most twice, by the choice of , we have . By Lemma 2.7 (ii), we have
Since there are at most ordered pairs , a union bound together with (4) and (5) gives . Hence there exists a spanning subgraph satisfying and for every pair satisfying with and .
Suppose that is not a robust -expander. Then there exists with and . Let . Since , we have and . Hence , a contradiction. Thus is a robust -expander.
Proof of thm:main
Let be given by Theorem 1.2. Choose constants such that . If , then , and the conclusion follows from Lemma 3.1. Next suppose that . If is odd, let be a perfect matching of , which exists by Ore’s theorem. Otherwise, set . By Lemma 3.4, there exists a spanning robust -expander with . Since , Lemma 3.3 gives a -factor of containing . Now is an even-regular graph containing , and hence is a robust -expander. Moreover, its degree is . Thus, by Theorem 1.2, has a Hamilton decomposition into pairwise edge-disjoint Hamilton cycles. Together with when is odd, these give the desired conclusion.
Finally, suppose that . By Lemma 2.4, contains a -factor . Since , Theorem 1.1 gives a decomposition of into Hamilton cycles and, when is odd, a perfect matching. This completes the proof.
Declaration of AI. The authors used GPT-6 Pro as a research assistance tool during the development of this work. In particular, the authors provided the AI with the paper [3]. With the assistance of GPT-6 Pro, an initial proof of Win’s conjecture was obtained. Building on this proof, the authors subsequently established the stronger result presented as Theorem 1.5.
The authors have carefully verified all mathematical arguments and proofs, and have independently revised and reorganized the manuscript to improve its mathematical precision, logical coherence, and readability. All results and proofs have been reviewed and approved by the authors, who take full responsibility for the correctness, originality, and final content of this paper.
References
- [1]B. Alspach, J.-C. Bermond and D. Sotteau, Decomposition into cycles I: Hamilton decompositions, in Cycles and Rays (Montreal, 1987), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 301, Kluwer, Dordrecht, 1990, 9–18.
- [2]J. A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976), 111–135.DOI
- [3]B. Csaba, D. Kühn, A. Lo, D. Osthus and A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures, Mem. Amer. Math. Soc. 244 (2016), no. 1154, v+164 pp.arxiv.org/abs/1401.4159
- [4]Y. Egawa, Edge-disjoint Hamiltonian cycles in graphs of Ore type, SUT J. Math. 29 (1993), 15–50.DOI
- [5]R. J. Faudree, C. C. Rousseau and R. H. Schelp, Edge-disjoint Hamiltonian cycles, in Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Mich., 1984), Wiley, New York, 1985, 231–249.
- [6]S. Janson, T. Łuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000.
- [8]D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: applications, J. Combin. Theory Ser. B 104 (2014), 1–27.DOI
- [9]J. Lai and W. Yan, An Ore-type condition for regular factors, arXiv:2608.24097 (2026).arxiv.org/abs/2608.24097
- [10]G. Li, Edge disjoint Hamilton cycles in graphs, J. Graph Theory 35 (2000), 8–20.
- [11]H. Lu and B. Ning, An Ore-type condition for large k-factor and disjoint perfect matchings, J. Graph Theory 94 (2020), 307–319.DOI
- [12]O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.DOI
- [13]W. T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952), 314–328.
- [14]S. Win, A sufficient condition for a graph to contain three disjoint 1-factors, J. Graph Theory 6 (1982), 489–492.DOI