betaFeedback

WorksMathematics

On Win's Conjecture for Edge-Disjoint Perfect Matchings

Abstract

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

Introduction

Graph decomposition problems form a central and active area of research in graph theory. A decomposition of a graph GG is a collection of pairwise edge-disjoint subgraphs whose edge sets partition E(G)E(G). If all these subgraphs are isomorphic to a prescribed graph HH, then the decomposition is called an HH-decomposition. The study of graph decompositions has a long history. A classical result of Walecki [1] shows that the complete graph K2m+1K_{2m+1} can be decomposed into mm Hamilton cycles, while K2mK_{2m} can be decomposed into m−1m-1 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 n0n_0 such that every rr-regular graph GG on n≥n0n \ge n_0 vertices with r≥⌊n/2⌋r \ge\lfloor n/2\rfloor admits a decomposition into ⌊r/2⌋\lfloor r/2\rfloor Hamilton cycles and, if rr is odd, one perfect matching.

Another important result is the Hamilton decomposition theorem of Kühn and Osthus [8] for robust expanders. For ν>0\nu> 0 and S⊆V(G)S \subseteq V(G), the robust ν\nu-neighborhood of SS is defined by RNG(S)={v∈V(G):∣NG(v)∩S∣≥νn}\mathrm{RN}_G(S)=\{v\in V(G): |N_G(v)\cap S|\ge\nu n\}. A graph GG of order nn is called a robust (ν,τ)(\nu,\tau)-expander if ∣RNG(S)∣≥∣S∣+νn|\mathrm{RN}_G(S)|\ge|S|+\nu n for every S⊆V(G)S\subseteq V(G) with τn≤∣S∣≤(1−τ)n\tau n\le|S|\le(1-\tau)n. Kühn and Osthus established the following result.

Theorem 1.2 (Kühn and Osthus [8]). For every α>0\alpha> 0, there exist constants τ>0\tau> 0 and ν0>0\nu_0 > 0 such that, for every 0<ν≤ν00 < \nu\le\nu_0, there exists an integer n0n_0 with the following property. Every even-regular robust (ν,τ)(\nu,\tau)-expander GG on n≥n0n \ge n_0 vertices with δ(G)≥αn\delta(G) \ge\alpha n admits a Hamilton decomposition.

This theorem is a key ingredient in the proof of Theorem 1.1. Indeed, for every fixed ε>0\varepsilon> 0, every graph GG with δ(G)≥(1/2+ε)n\delta(G) \ge(1/2+\varepsilon)n is a robust (ν,τ)(\nu,\tau)-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 GG, let σ2(G)\sigma_2(G) denote the minimum of dG(x)+dG(y)d_G(x)+d_G(y) over all pairs of distinct nonadjacent vertices x,yx,y, with σ2(Kn)=+∞\sigma_2(K_n)=+\infty. Win [14] proposed the following conjecture for edge-disjoint perfect matchings.

Conjecture 1.3 (Win [14]). Let nn be even and 1≤k≤n−21 \le k \le n-2. If an nn-vertex graph GG satisfies σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2, then GG contains kk pairwise edge-disjoint perfect matchings.

The cases k=1,2k=1,2 follow from Ore’s theorem [12], while Win [14] established the case k=3k=3. For every fixed even kk, the Hamilton cycle packing theorem of Faudree, Rousseau and Schelp [5] also implies Conjecture 1.3 for sufficiently large nn. A substantial advance was made by Lu and Ning [11], who confirmed the conjecture for all k≥n/2k \ge n/2 when nn is sufficiently large. We state their result explicitly.

Theorem 1.4 (Lu and Ning [11]). There exists an integer n0n_0 such that, whenever n≥n0n \ge n_0 is even and n/2≤k≤n−2n/2 \le k \le n-2, every nn-vertex graph GG satisfying σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2 contains kk pairwise edge-disjoint perfect matchings.

In this paper, we confirm Conjecture 1.3 for all sufficiently large even nn independent of kk. 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 n0n_0 such that, whenever n≥n0n \ge n_0 is even, 1≤k≤n−21 \le k \le n-2, and GG is an nn-vertex simple graph satisfying σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2, the following assertions hold. If kk is even, then GG contains k/2k/2 pairwise edge-disjoint Hamilton cycles. If kk is odd, then GG contains (k−1)/2(k-1)/2 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 nn.

Corollary 1.6. There exists an integer n0n_0 such that, for every even n≥n0n \ge n_0 and every integer 1≤k≤n−21 \le k \le n-2, each nn-vertex graph GG with σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2 contains kk pairwise edge-disjoint perfect matchings.

Preliminaries

Notation

All graphs are finite, simple and undirected. For a vertex vv of GG, let NG(v)N_G(v) and dG(v)d_G(v) denote its neighborhood and degree, respectively. We write NG[v]=NG(v)∪{v}N_G[v]=N_G(v)\cup\{v\} for the closed neighborhood of vv. The minimum and maximum degrees are δ(G)=min⁡v∈V(G)dG(v)\delta(G)=\min_{v\in V(G)}d_G(v) and Δ(G)=max⁡v∈V(G)dG(v)\Delta(G) = \max_{v\in V(G)} d_G(v). A vertex cut, or simply a cut, of GG is a set S⊆V(G)S \subseteq V(G) such that G−SG-S is disconnected or has at most one vertex, the vertex connectivity κ(G)\kappa(G) is the minimum size of such a set. For any A,B⊆V(G)A, B \subseteq V(G), let eG(A,B)=∑v∈A∣NG(v)∩B∣e_G(A,B) = \sum_{v\in A} |N_G(v) \cap B|. In particular, edges with both endpoints in A∩BA \cap B are counted twice. A kk-factor is a spanning kk-regular subgraph.

Useful tools

We begin by recalling several results that will be used in our proofs.

Lemma 2.1 (Egawa [4]). Let r≥2r \ge2 and n≥44(r−1)n \ge44(r-1). If an nn-vertex graph GG satisfies σ2(G)≥n\sigma_2(G) \ge n and δ(G)≥4r−2\delta(G) \ge4r-2, then GG contains rr pairwise edge-disjoint Hamilton cycles.

Lemma 2.2 (Li [10]). Let r≥1r \ge1 and let GG be a 2r2r-connected graph on nn vertex. If every pair of vertices x,yx,y at distance two satisfies max⁡{dG(x),dG(y)}≥n/2+2r−2\max\{d_G(x),d_G(y)\} \ge n/2 + 2r - 2, then GG contains rr pairwise edge-disjoint Hamilton cycles.

Lemma 2.3 (Bondy and Chvátal [2]). Let GG be an nn-vertex graph, and let x,yx,y be nonadjacent vertices of GG. If dG(x)+dG(y)≥nd_G(x) + d_G(y) \ge n, then GG is Hamiltonian if and only if G+xyG+xy is Hamiltonian.

Lemma 2.4 (Lu and Ning [11]). Let n/2≤k≤n−1n/2 \le k \le n-1 with knkn even. If GG is an nn-vertex graph satisfying σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2, then GG contains a kk-factor.

For a function f:V(G)→Nf: V(G) \to\mathbb{N}, an ff-factor of GG is a spanning subgraph FF such that dF(v)=f(v)d_F(v) = f(v) for every v∈V(G)v \in V(G). We also use Tutte’s ff-factor theorem [13]. For a graph GG and f:V(G)→Nf: V(G) \to\mathbb{N}, write f(X)=∑v∈Xf(v)f(X) = \sum_{v\in X} f(v).

Lemma 2.5 (Tutte [13]). A graph GG has an ff-factor if and only if, for all disjoint sets S,T⊆V(G)S,T \subseteq V(G), f(S)+∑v∈T(dG−S(v)−f(v))≥q(S,T)f(S) + \sum_{v\in T}(d_{G-S}(v)-f(v)) \ge q(S,T), where q(S,T)q(S,T) count the components CC of G−S−TG-S-T for which f(V(C))+eG(V(C),T)f(V(C)) + e_G(V(C),T) 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 1≤k≤n−21 \le k \le n-2, and let GG be an nn-vertex graph satisfying σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2. Then κ(G)≥k\kappa(G) \ge k. Moreover, if n>2kn > 2k and κ(G)=k\kappa(G) = k, there is an edge ab∉E(G)ab \notin E(G) such that κ(G+ab)≥k+1\kappa(G+ab) \ge k+1.

Proof. Suppose that SS is a vertex cut of GG. Let A,BA,B be two distinct components of G−SG-S. For any x∈Ax \in A and y∈By \in B, we have

n+k−2≤dG(x)+dG(y)≤∣A∣+∣B∣+2∣S∣−2≤n+∣S∣−2.(1)n+k-2 \le d_G(x)+d_G(y) \le|A|+|B|+2|S|-2 \le n+|S|-2. \tag*{(1)}

Thus ∣S∣≥k|S| \ge k, giving κ(G)≥k\kappa(G) \ge k.

If κ(G)=k\kappa(G)=k and ∣S∣=k|S|=k. Then equality in (2) holds throughout, so G−SG-S consists of exactly two cliques G[A]G[A] and G[B]G[B], and every vertex of SS is adjacent to every vertex of A∪BA \cup B.

Assume n>2kn > 2k. Choose a∈Aa \in A and b∈Bb \in B, and let G1=G+abG_1 = G+ab. For any T⊆V(G)T \subseteq V(G) with ∣T∣≤k|T| \le k, if T=ST=S, then G1−TG_1-T is connected by the edge abab. Otherwise, S∖T≠∅S \setminus T \ne\varnothing and (A∪B)∖T(A \cup B) \setminus T, since ∣A∪B∣=n−k>k|A \cup B| = n-k > k. As all edges between these two nonempty sets are present, G1−TG_1-T is connected. Hence κ(G1)≥k+1\kappa(G_1) \ge k+1.

Lemma 2.7 (Chernoff bound [6]). Let XX be a sum of independent Bernoulli random variables with μ=E[X]\mu= \mathbb{E}[X]. Then the following holds:

  1. For every δ>0\delta> 0, P(X≥(1+δ)μ)≤exp⁡(−δ2μ2+δ)\mathbb{P}(X \ge(1+\delta)\mu) \le\exp\left(-\frac{\delta^2\mu}{2+\delta}\right).

  2. For every 0<δ<10 < \delta< 1, P(X≤(1−δ)μ)≤exp⁡(−δ2μ2)\mathbb{P}(X \le(1-\delta)\mu) \le\exp\left(-\frac{\delta^2\mu}{2}\right).

Proof of main Theorem

Small kk case.

The next lemma deals with the range of small kk.

Lemma 3.1. Let nn be even, 1≤k≤n−21 \le k \le n - 2, and n≥22kn \ge22k. Every nn-vertex graph GG with σ2(G)≥n+k−2\sigma_2(G) \ge n + k - 2 satisfies the conclusion of Theorem 1.5.

Proof. For k=1k = 1, add a universal vertex to GG. The resulting (n+1)(n + 1)-vertex graph meets Ore’s condition and has a Hamilton cycle; deleting the new vertex yields a Hamilton path in GG, which contains a perfect matching since nn is even. For k=2k = 2, Ore’s theorem supplies a Hamilton cycle directly.

Now suppose k≥3k \ge3 and let r=⌈k/2⌉r = \lceil k/2\rceil. We first show that if GG is 2r2r-connected then it contains rr pairwise edge-disjoint Hamilton cycles.

Starting from G:=G1G := G_1, we can add an edge xy∉E(Gi)xy \notin E(G_i) whenever dGi(x)+dGi(y)≥n+4r−4d_{G_i}(x) + d_{G_i}(y) \ge n + 4r - 4. This process terminates with a sequence G1⊆G2⊆⋯⊆GtG_1 \subseteq G_2 \subseteq\cdots\subseteq G_t such that every pair of nonadjacent vertices x,yx,y in GtG_t satisfies dGt(x)+dGt(y)<n+4r−4d_{G_t}(x) + d_{G_t}(y) < n + 4r - 4.

We claim that adding edge preserves the existence of rr edge-disjoint Hamilton cycles. Indeed, suppose there are rr edge-disjoint Hamilton cycles C1,…,CrC_1,\ldots,C_r in Gi+xyG_i+xy, and at most one of its cycles uses xyxy, say CrC_r. Let H=Gi−⋃i<rE(Ci)H = G_i - \bigcup_{i<r} E(C_i). Then H+xyH+xy is Hamiltonian and dH(x)+dH(y)≥n+4r−4−4(r−1)≥nd_H(x) + d_H(y) \ge n + 4r - 4 - 4(r - 1) \ge n, by Lemma 2.3, HH has a Hamilton cycle Cr′C'_r, combining with C1,…,Cr−1C_1,\ldots,C_{r-1}, there are rr edge-disjoint Hamilton cycles in GiG_i.

It remains to find rr edge-disjoint Hamilton cycles in GtG_t. If δ(Gt)≥4r−2\delta(G_t) \ge4r - 2, then Lemma 2.1 applies, since σ2(Gt)≥n+k−2\sigma_2(G_t) \ge n + k - 2. Otherwise, choose x∈V(Gt)x \in V(G_t) with dGt(x)=d≤4r−3d_{G_t}(x) = d \le4r - 3, and let B=V(Gt)∖NGt[x]B = V(G_t) \setminus N_{G_t}[x]. Each b∈Bb \in B satisfies dGt(b)≥n+k−2−d>n−dd_{G_t}(b) \ge n + k - 2 - d > n - d.

Now let vv be any vertex with dGt(v)≥n/2d_{G_t}(v) \ge n/2. If vv is nonadjacent to some b∈B∖{v}b \in B \setminus\{v\}, then dGt(v)+dGt(b)≥n2+n−d≥n+4r−4d_{G_t}(v) + d_{G_t}(b) \ge\frac{n}{2} + n - d \ge n + 4r - 4, where the last inequality follows from n≥44(r−1)n \ge44(r - 1) and d≤4r−3d \le4r - 3. This contradicts the construction of GtG_t. Thus vv is adjacent to every vertex of B∖{v}B \setminus\{v\}, and hence dGt(v)≥∣B∣−1=n−d−2≥n2+2r−2d_{G_t}(v) \ge|B| - 1 = n - d - 2 \ge\frac{n}{2} + 2r - 2. Since σ2(Gt)≥n\sigma_2(G_t) \ge n, every pair of vertices at distance two has at least one endpoint of degree at least n/2n/2. Consequently, max⁡{dGt(u),dGt(v)}≥n2+2r−2\max\{d_{G_t}(u),d_{G_t}(v)\} \ge\frac{n}{2} + 2r - 2 for every pair u,vu,v at distance two. As GtG_t is 2r2r-connected, Lemma 2.2 yields rr edge-disjoint Hamilton cycles in GtG_t, and hence also in GG.

By Proposition 2.6, κ(G)≥k\kappa(G) \ge k. If k=2rk = 2r, then GG is 2r2r-connected, and the preceding argument gives rr edge-disjoint Hamilton cycles in GG. Assume that k=2r−1k = 2r - 1, then κ(G)≥2r−1\kappa(G) \ge2r - 1. If κ(G)=2r−1\kappa(G) = 2r - 1, by Proposition 2.6, there exist an edge e∉E(G)e \notin E(G) such that G′=G+eG' = G + e is 2r2r-connected, otherwise, set G′=GG' = G. Applying the preceding argument again, we obtain rr edge-disjoint Hamilton cycles in G′G'. At most one of these cycles uses ee, if added. Deleting ee from that cycle if necessary (or any edge otherwise) yields a Hamilton path in GG edge-disjoint from the remaining r−1r - 1 Hamilton cycles. Since nn is even, this path contains a perfect matching, as required.

Extension to regular factors

Proposition 3.2. Let GG be an nn-vertex graph satisfying σ2(G)≥n+k−2\sigma_2(G) \ge n + k - 2. For any subsets X,Y⊆V(G)X,Y \subseteq V(G) with ∣X∣+∣Y∣>0|X| + |Y| > 0, we have

eG(X,Y)≥∣X∣∣Y∣(∣X∣+∣Y∣−n+k)∣X∣+∣Y∣−∣X∩Y∣.e_G(X,Y) \ge\frac{|X||Y|(|X|+|Y|-n+k)}{|X|+|Y|} - |X \cap Y|.

Proof. The inequality is trivial if either XX or YY is empty. Thus we may assume ∣X∣,∣Y∣>0|X|,|Y| > 0. Let HH be the bipartite graph with vertex classes given by disjoint copies of XX and YY, in which there is an edge between x∈Xx \in X and y∈Yy \in Y if and only if x≠yx \ne y and xy∉E(G)xy \notin E(G). Consequently, for every xy∈E(H)xy \in E(H), dH(x)+dH(y)≤dG(x)+dG(y)≤n−kd_H(x) + d_H(y) \le d_G(x) + d_G(y) \le n-k. Then, we have

∣E(H)∣2∣X∣+∣E(H)∣2∣Y∣≤∑v∈V(H)dH(v)2=∑xy∈E(H)(dH(x)+dH(y))≤(n−k)∣E(H)∣.\frac{|E(H)|^2}{|X|}+\frac{|E(H)|^2}{|Y|}\le\sum_{v\in V(H)}d_H(v)^2=\sum_{xy\in E(H)}(d_H(x)+d_H(y))\le(n-k)|E(H)|.

Hence ∣E(H)∣≤(n−k)∣X∣∣Y∣/(∣X∣+∣Y∣)|E(H)|\le(n-k)|X||Y|/(|X|+|Y|). Since ∣X∣∣Y∣=eG(X,Y)+∣E(H)∣+∣X∩Y∣|X||Y|=e_G(X,Y)+|E(H)|+|X\cap Y|, the claim follows.

Lemma 3.3. For every 0<α≤1/20<\alpha\le1/2, there exist ε>0\varepsilon>0 and n0=n0(α)n_0=n_0(\alpha) such that the following holds. Let n≥n0n\ge n_0, αn≤k≤n/2\alpha n\le k\le n/2 with knkn even, and let GG be an nn-vertex graph satisfying σ2(G)≥n+k−2\sigma_2(G)\ge n+k-2. Then every H⊆GH\subseteq G with Δ(H)≤εn\Delta(H)\le\varepsilon n is contained in a kk-factor of GG.

Proof. Choose constants

0<1/n0≪ε≪c≪η≪α≤1/2.(2)0<1/n_0\ll\varepsilon\ll c\ll\eta\ll\alpha\le1/2. \tag*{(2)}

Let H⊆GH\subseteq G with Δ(H)≤εn\Delta(H)\le\varepsilon n, and put G′=G−E(H)G'=G-E(H). We claim that κ(G′)≥k−2εn\kappa(G')\ge k-2\varepsilon n. By Proposition 2.6, δ(G′)≥δ(G)−Δ(H)≥k−εn\delta(G')\ge\delta(G)-\Delta(H)\ge k-\varepsilon n. Suppose that G′−WG'-W is disconnected for some W⊆V(G)W\subseteq V(G) with ∣W∣<k−2εn|W|<k-2\varepsilon n. For every component CC of G′−WG'-W and every v∈Cv\in C, we have dG′(v)≤∣C∣−1+∣W∣d_{G'}(v)\le|C|-1+|W|, which implies ∣C∣>εn|C|>\varepsilon n. Let C1,C2C_1,C_2 be two distinct components of G′−WG'-W. Since eG′(C1,C2)=0e_{G'}(C_1,C_2)=0, every edge of GG between C1C_1 and C2C_2 must belong to HH. If all edges between C1C_1 and C2C_2 were present in GG, then dH(x)≥∣C2∣>Δ(H)d_H(x)\ge|C_2|>\Delta(H) for any x∈C1x\in C_1, a contradiction. Thus there exist x∈C1x\in C_1 and y∈C2y\in C_2 such that xy∉E(G)xy\notin E(G). Consequently, dG(x)+dG(y)≤∣C1∣+∣C2∣+2∣W∣+2εn−2≤n+∣W∣+2εn−2<n+k−2d_G(x)+d_G(y)\le|C_1|+|C_2|+2|W|+2\varepsilon n-2\le n+|W|+2\varepsilon n-2<n+k-2, contrary to the Ore condition. Hence κ(G′)≥k−2εn\kappa(G')\ge k-2\varepsilon n.

Define f(v)=k−dH(v)f(v)=k-d_H(v) for every v∈V(G)v\in V(G). Then f(v)≥0f(v)\ge0 and f(V(G))=kn−2e(H)f(V(G))=kn-2e(H) is even. Let S,TS,T be disjoint subsets of V(G)V(G), we have

f(S)+∑v∈T(dG′−S(v)−f(v))=k(∣S∣−∣T∣)−dH(S)+dH(T)+eG′(T,V(G)∖S)=k(∣S∣−∣T∣)−dH(S)+eG(T,V(G)∖S)+eH(S,T)≥k(∣S∣−∣T∣)+eG(T,V(G)∖S)−εn∣S∣.(3)\begin{aligned} f(S)+\sum_{v\in T}(d_{G'-S}(v)-f(v)) &=k(|S|-|T|)-d_H(S)+d_H(T)+e_{G'}(T,V(G)\setminus S)\\ &=k(|S|-|T|)-d_H(S)+e_G(T,V(G)\setminus S)+e_H(S,T)\\ &\ge k(|S|-|T|)+e_G(T,V(G)\setminus S)-\varepsilon n|S|. \tag*{(3)} \end{aligned}

Suppose first that ∣S∣+∣T∣≤ηn|S|+|T|\le\eta n. Since κ(G′)≥k−2εn>ηn\kappa(G')\ge k-2\varepsilon n>\eta n, G′−S−TG'-S-T is connected, so q(S,T)≤1q(S,T)\le1. By δ(G)≥k\delta(G)\ge k, we have eG(T,V(G)∖S)≥∣T∣(k−∣S∣)e_G(T,V(G)\setminus S)\ge|T|(k-|S|). Thus, the left-hand side of (3) is at least ∣S∣(k−∣T∣−εn)≥0|S|(k-|T|-\varepsilon n)\ge0. Since f(V(G))f(V(G)) is even and

f(S)+∑v∈T(dG′−S(v)−f(v))≡q(S,T)(mod2)f(S)+\sum_{v\in T}(d_{G'-S}(v)-f(v))\equiv q(S,T)\pmod2

implies that f(S)+∑v∈T(dG′−S(v)−f(v))≥q(S,T)f(S)+\sum_{v\in T}(d_{G'-S}(v)-f(v))\ge q(S,T). Now suppose that ∣S∣+∣T∣>ηn|S|+|T|>\eta n.

Let h=∣S∣−∣T∣h=|S|-|T|. If h>k/2h>k/2, then k(∣S∣−∣T∣)+eG(T,V(G)∖S)≥k2/2≥cn2k(|S|-|T|)+e_G(T,V(G)\setminus S)\ge k^2/2\ge cn^2. Otherwise, h≤k/2h\le k/2. Applying Proposition 3.2 and using ∣T∣(n−∣S∣)=∣S∣(n−∣T∣)−nh|T|(n-|S|)=|S|(n-|T|)-nh, we obtain k(∣S∣−∣T∣)+eG(T,V(G)∖S)k(|S|-|T|)+e_G(T,V(G)\setminus S) is greater than

(n−k)h2+(k−h)∣S∣(n−∣T∣)n−h−∣T∣≥nh2/2+k∣S∣2/22n−n≥α20(∣S∣+∣T∣)2−n≥cn2−n.\frac{(n-k)h^2+(k-h)|S|(n-|T|)}{n-h}-|T|\ge\frac{nh^2/2+k|S|^2/2}{2n}-n\ge\frac{\alpha}{20}(|S|+|T|)^2-n\ge cn^2-n.

By (2) and αn≤k≤n/2\alpha n\le k\le n/2. Thus, in all cases, k(∣S∣−∣T∣)+eG(T,V(G)∖S)≥cn2−nk(|S|-|T|)+e_G(T,V(G)\setminus S)\ge cn^2-n. Consequently, by (3), f(S)+∑v∈T(dG′−S(v)−f(v))≥(c−ε)n2−n>n≥q(S,T)f(S)+\sum_{v\in T}(d_{G'-S}(v)-f(v))\ge(c-\varepsilon)n^2-n>n\ge q(S,T). Thus Lemma 2.5 holds for all disjoint sets S,T⊆V(G)S,T\subseteq V(G) and G′G' has an ff-factor. Thus, GG has a kk-factor containing all the edge of HH.

Construction of robust expanders

Lemma 3.4. For every 0<α≤1/20 < \alpha\le1/2 and 0<ε,τ<1/20 < \varepsilon,\tau< 1/2, there exist ν>0\nu> 0 and n0n_0 such that the following holds. Let n≥n0n \ge n_0, αn≤k≤n/2\alpha n \le k \le n/2, and let GG be an nn-vertex graph satisfying σ2(G)≥n+k−2\sigma_2(G) \ge n+k-2. Then, for every matching MM in GG, there exists a spanning robust (ν,τ)(\nu,\tau)-expander R⊆G−E(M)R \subseteq G-E(M) with Δ(R)≤εn/2\Delta(R) \le\varepsilon n/2.

Proof. Choose constants such that 1/n0≪ν≪α,τ,ε≤1/21/n_0 \ll\nu\ll\alpha,\tau,\varepsilon\le1/2. Select each edge of G−E(M)G-E(M) independently with probability ε/8\varepsilon/8, and let RR be the resulting spanning graph. For every v∈V(G)v \in V(G), E(dR(v))≤εn/8\mathbb{E}(d_R(v)) \le\varepsilon n/8. By Lemma 2.7,

P(dR(v)≥εn/2)≤exp⁡(−9εn/40)≤exp⁡(−νn).(4)\mathbb{P}\left(d_R(v) \ge\varepsilon n/2\right) \le\exp(-9\varepsilon n/40) \le\exp(-\nu n). \tag*{(4)}

Let A,B⊆V(G)A,B \subseteq V(G) satisfy ∣A∣,∣B∣≥τn/2|A|,|B| \ge\tau n/2 and ∣A∣+∣B∣≥(1−α/2)n|A|+|B| \ge(1-\alpha/2)n. Since ∣A∣∣B∣/(∣A∣+∣B∣)≥τn/4|A||B|/(|A|+|B|) \ge\tau n/4 and ∣A∣+∣B∣−n+k≥αn/2|A|+|B|-n+k \ge\alpha n/2, by Proposition 3.2, and noting that removing a matching deletes at most nn edges, we obtain

eG−E(M)(A,B)≥∣A∣∣B∣(∣A∣+∣B∣−n+k)∣A∣+∣B∣−2n≥ατ16n2.e_{G-E(M)}(A,B) \ge\frac{|A||B|(|A|+|B|-n+k)}{|A|+|B|}-2n \ge\frac{\alpha\tau}{16}n^2.

at least ατn2/32≥2νn2\alpha\tau n^2/32 \ge2\nu n^2 distinct edges are counted by eG−E(M)(A,B)e_{G-E(M)}(A,B). Let XX be the number of distinct edges counted by eG−E(M)(A,B)e_{G-E(M)}(A,B) that are selected into RR. Since each edge is counted at most twice, by the choice of ν\nu, we have E[X]=eG−E(M)(A,B)⋅ε/16≥8νn2\mathbb{E}[X]=e_{G-E(M)}(A,B)\cdot\varepsilon/16 \ge8\nu n^2. By Lemma 2.7 (ii), we have

P(eR(A,B)<2νn2)≤P(X<2νn2)≤P(X<E(X)/2)≤exp⁡(−νn2).(5)\mathbb{P}\left(e_R(A,B)<2\nu n^2\right) \le\mathbb{P}\left(X<2\nu n^2\right) \le\mathbb{P}\left(X<\mathbb{E}(X)/2\right) \le\exp(-\nu n^2). \tag*{(5)}

Since there are at most 4n4^n ordered pairs (A,B)(A,B), a union bound together with (4) and (5) gives nexp⁡(−νn)+4nexp⁡(−νn2)<1n\exp(-\nu n)+4^n\exp(-\nu n^2)<1. Hence there exists a spanning subgraph R⊆G−E(M)R\subseteq G-E(M) satisfying Δ(R)≤εn/2\Delta(R)\le\varepsilon n/2 and eR(A,B)≥2νn2e_R(A,B)\ge2\nu n^2 for every pair A,BA,B satisfying A,B⊆V(G)A,B\subseteq V(G) with ∣A∣,∣B∣≥τn/2|A|,|B|\ge\tau n/2 and ∣A∣+∣B∣≥(1−α/2)n|A|+|B|\ge(1-\alpha/2)n.

Suppose that RR is not a robust (ν,τ)(\nu,\tau)-expander. Then there exists X⊆V(G)X\subseteq V(G) with τn≤∣X∣≤(1−τ)n\tau n\le|X|\le(1-\tau)n and ∣RNR(X)∣<∣X∣+νn|RN_R(X)|<|X|+\nu n. Let Y=V(G)∖RNR(X)Y=V(G)\setminus RN_R(X). Since ν≪τ,α\nu\ll\tau,\alpha, we have ∣X∣,∣Y∣≥τn/2|X|,|Y|\ge\tau n/2 and ∣X∣+∣Y∣>(1−α/2)n|X|+|Y|>(1-\alpha/2)n. Hence 2νn2≤eR(X,Y)<νn∣Y∣≤νn22\nu n^2\le e_R(X,Y)<\nu n|Y|\le\nu n^2, a contradiction. Thus RR is a robust (ν,τ)(\nu,\tau)-expander. □\square

Proof of thm:main

Let τ,ν0>0\tau,\nu_0>0 be given by Theorem 1.2. Choose constants 1/n0≪ν≪ε≪τ≪α≤1/221/n_0\ll\nu\ll\varepsilon\ll\tau\ll\alpha\le1/22 such that ν≤ν0\nu\le\nu_0. If k≤αnk\le\alpha n, then n≥22kn\ge22k, and the conclusion follows from Lemma 3.1. Next suppose that αn<k<n/2\alpha n<k<n/2. If kk is odd, let MM be a perfect matching of GG, which exists by Ore’s theorem. Otherwise, set M=∅M=\varnothing. By Lemma 3.4, there exists a spanning robust (ν,τ)(\nu,\tau)-expander R⊆G−E(M)R\subseteq G-E(M) with Δ(R)≤εn/2\Delta(R)\le\varepsilon n/2. Since Δ(R∪M)≤εn\Delta(R\cup M)\le\varepsilon n, Lemma 3.3 gives a kk-factor FF of GG containing R∪MR\cup M. Now F−E(M)F-E(M) is an even-regular graph containing RR, and hence is a robust (ν,τ)(\nu,\tau)-expander. Moreover, its degree is 2⌊k/2⌋≥αn/22\lfloor k/2\rfloor\ge\alpha n/2. Thus, by Theorem 1.2, F−E(M)F-E(M) has a Hamilton decomposition into ⌊k/2⌋\lfloor k/2\rfloor pairwise edge-disjoint Hamilton cycles. Together with MM when kk is odd, these give the desired conclusion.

Finally, suppose that k≥n/2k\ge n/2. By Lemma 2.4, GG contains a kk-factor FF. Since k≥n/2k\ge n/2, Theorem 1.1 gives a decomposition of FF into ⌊k/2⌋\lfloor k/2\rfloor Hamilton cycles and, when kk 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. [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. [2]J. A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976), 111–135.DOI
  3. [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. [4]Y. Egawa, Edge-disjoint Hamiltonian cycles in graphs of Ore type, SUT J. Math. 29 (1993), 15–50.DOI
  5. [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. [6]S. Janson, T. Łuczak and A. Ruciński, Random Graphs, Wiley, New York, 2000.
  7. [8]D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: applications, J. Combin. Theory Ser. B 104 (2014), 1–27.DOI
  8. [9]J. Lai and W. Yan, An Ore-type condition for regular factors, arXiv:2608.24097 (2026).arxiv.org/abs/2608.24097
  9. [10]G. Li, Edge disjoint Hamilton cycles in graphs, J. Graph Theory 35 (2000), 8–20.
  10. [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
  11. [12]O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.DOI
  12. [13]W. T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952), 314–328.
  13. [14]S. Win, A sufficient condition for a graph to contain three disjoint 1-factors, J. Graph Theory 6 (1982), 489–492.DOI

Paper details

vlnc:W_zredqypf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents