Paperlane

no. 16 · Tuesday 17 November 2026

On Win's Conjecture for Edge-Disjoint Perfect Matchings

Yufei Chang, Yangyang Cheng, Zhilan Wang and Shuo Wei

math.CO · 8 pp

Abstract

In 1982, Win conjectured that, for every even integer $n$ and every integer $k$ $1\le k\le n-2$, any graph $G$ of order $n$ satisfying $d_G(x)+d_G(y)\ge n+k-2$ for every pair of nonadjacent vertices $x,y$ contains $k$ pairwise edge-disjoint perfect matchings. In this paper, we prove a stronger result for all sufficiently large even $n$. More precisely, we show that under the same degree-sum condition, $G$ contains $\lfloor k/2\rfloor$ pairwise edge-disjoint Hamilton cycles, together with an additional perfect matching when $k$ is odd, all pairwise edge-disjoint. Consequently, we confirm Win's conjecture for all sufficiently large even $n$, with a threshold independent of $k$.

comments
8 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.20093 ↗