Edge Disjoint Cycles Through Specified Vertices

Luis Goddyn^{∗} Ladislav Stacho^{†}

Department of Mathematics Simon Fraser University, Burnaby, BC, Canada

                   goddyn@math.sfu.ca, lstacho@math.sfu.ca

February 18, 2005

Abstract

We give a sufficient condition for a simple graph G to have k pairwise edge-disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G[W] be 2k-connected, and that for any two vertices at distance two in G[W], at least one of the two has degree at least |V (G)|/2 + 2(k − 1) in G. This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k = 1) and Li (where W = V (G)).

A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X, Y. If G is 2k connected, then G contains k Hamilton cycles which are pairwise edge-disjoint except for edges in G[Y].

Keywords: Hamilton cycle, Hamilton circuit, connectivity, prescribed vertices, Ore condition, Fan condition, packing cycles, long cycle.

1 Introduction

In this paper we give a sufficient condition for a simple graph to have k pairwise edge-disjoint cycles, where every cycle contains a prespecified set of vertices. We state the main result.

Theorem 1 Let G = (V (G), E(G)) be a finite undirected simple graph of order n, let W ⊆ V (G), |W | ≥ 3, and let k be a positive integer. Suppose that G[W] is 2k-connected, and that

max{d_{G}(u), d_{G}(v)} ≥ n/2 + 2(k − 1)

for every u, v ∈ W such that dist_{G[W]}(u, v) = 2. Then G contains k pairwise edge-disjoint cycles C_{1}, …, C_{k} such that W ⊆ V (C_{i}), 1 ≤ i ≤ k.

(Here, d_{G}(v) is the degree of v in G, G[W] is the subgraph induced by W, and dist_{G}(u, v) is the distance from u to v in G.)

The degree condition on W is in the spirit of Fan [3]. This Fan-type hypothesis gives a slightly stronger result than the corresponding Ore-type condition (that d_{G}(u) + d_{G}(v) ≥ n + 4(k − 1) for u, v ∈ W, uv ∉ E). In [4], this degree condition was weakened (for sufficiently large n) to the best possible bound d_{G}(u) + d_{G}(v) ≥ n + 2(k − 1).

∗Research supported by the Natural Sciences and Engineering Research Council of Canada.

†Research supported by the Natural Sciences and Engineering Research Council of Canada.

Theorem 1 is a common generalization of previous results concerning the two special cases k = 1 and W = V. The case k = 1 is proved, in essence, by Bollobás and Brightwell [1]. Their result is stated with the Ore-type degree hypothesis, which implies 2-connectivity. The special case W = V is presented by Li [8] in 2000 as a slight sharpening of Li and Chen [9]. A related line of research concerning the case W = V is pursued in [2, 7, 11]. They show that if n ≫ k, then G has k edge-disjoint Hamilton cycles even after relaxing our hypothesis. In particular, they replace our Fan-type and connectivity conditions with a relaxed Ore-type condition (d_{G}(u) + d_{G}(v) ≥ n), and a minimum degree condition. Some of our techniques are borrowed from [4, 8]. For further results on Hamilton cycles in graphs we refer the reader to [5, 6].

The proof of Theorem 1 proceeds in two steps. First we prove the following lemma, which we regard to be of equal importance to the main theorem.

Lemma 2 Let G = (X ∪ Y, E) be a 2k-connected graph such that X and Y are disjoint cliques in G. Then G contains k Hamilton cycles C_{1}, …, C_{k} such that e ∈ E(C_{i}) ∩ E(C_{j}) implies e ∈ E(G[Y]), for 1 ≤ i < j ≤ k. Moreover if |Y | ≥ k + 1, then each C_{i} contains an edge in G[Y].

The special case |Y | = 1 of Lemma 2 is (essentially) the well known decomposition of K_{2k+1} into Hamilton cycles. Our proof of Lemma 2 is inspired by Li’s argument in [8]. However, Li requires the additional hypothesis |Y | ≥ 2k. Dropping Li’s hypothesis results in significant complications. The proof of Lemma 2 is presented in Section 3. The second step (Section 4) is to derive Theorem 1 from Lemma 2.

2 Notation and Auxiliary Results

All graphs G = (V (G), E(G)) are simple graphs. Let x, y ∈ V (G) and let X, Y ⊆ V (G). Then dist_{G}(x, y) is the distance from x to y in G. We denote by N_{G}(X, Y) the set of vertices in Y which are adjacent in G to at least one vertex in X. We may write N_{G}(x, Y) instead of N_{G}({x}, Y), and N_{G}(x) instead of N_{G}(x, V (G)). We denote by d_{G}(X, Y), d_{G}(x, Y) and d_{G}(x) the respective cardinalities |N_{G}(X, Y)|, |N_{G}(x, Y)| and |N_{G}(x)|. The set of edges in G with one end in X and one end in Y is denoted E_{G}(X, Y). We write e_{G}(X, Y) for |E_{G}(X, Y)|. A u, v-path is a path whose endpoints are vertices u and v. A cycle C ⊆ G goes through W if W ⊆ V (C).

Let Q ⊆ V (G). A vertex pair {a, b} ⊆ V (G) − Q is Q-linked in G if there exist edges e_{1} = aq_{1}, e_{2} = bq_{2} in G such that q_{1}, q_{2} are distinct vertices in Q. A collection of subgraphs in G is edge-disjoint outside of Q if every edge of G which belongs to at least two of the subgraphs has both its endpoints in Q.

In Figure 2, we depict Walecki’s famous decomposition of K_{2k+1} into Hamilton cycles, as described by Lucas [10].

Proposition 3 For ℓ ≥ 2k + 1, the graph K_{ℓ} contains k pairwise edge-disjoint Hamilton cycles.

By deleting vertex 2k from Walecki’s construction, we obtain a decomposition of K_{2k} into k Hamilton paths. Let m ≤ ⌊k/2⌋, and consider the m Hamilton paths whose endpoints are the vertex pairs {1, 2}, {3, 4}, …, {2m − 1, 2m}. We observe that each of these Hamilton paths

Figure 1: Walecki’s decomposition: Rotate the depicted Hamilton cycle k times.

contains an edge joining 0 to a vertex in the set {k+1, k+3, k+5, …, k+2m−1}. By relabeling vertices appropriately, the following result follows easily.

Proposition 4 Let H be a complete graph of order n. Let u_{1}, v_{1}, u_{2}, v_{2}, …, u_{k}, v_{k} be distinct vertices of H, where k ≤ n/2. Let S ⊆ V (H) have cardinality ≥ m+1, where −1 ≤ m ≤ n/4, and such that u_{j}, v_{j} ∉ S for j ≤ m. Then H has pairwise edge-disjoint Hamilton paths P_{1}, …, P_{k}, where P_{i} has endpoints u_{i}, v_{i}, 1 ≤ i ≤ k, and where P_{j} contains an edge with both endpoints in S, 1 ≤ j ≤ m.

Let Q, R, X be a partition of V (G) so that X and Q ∪ R are both cliques in G. There are several places in this paper where we need to construct a Hamilton cycle in G starting with a Hamilton path P in G − Q. We give two constructions. Let {u, v} be the endpoints of P.

Extension 1 Suppose {u, v} is Q-linked in G. Then we may extend P to a Hamilton cycle of G by adding a Hamilton u, v-path in G[Q ∪ {u, v}].

Extension 2 Suppose u, v have a common neighbour q ∈ Q, and that there exists e = ab ∈ E(P) where a, b ∈ R. Then we may extend P − e to a Hamilton cycle of G by adding the path u, q, v and adding an a, b-Hamilton path in G[Q − {q} ∪ {a, b}]. This construction makes sense even if Q = {q}.

Let P_{1}, P_{2}, …, P_{k} be pairwise edge-disjoint Hamilton paths in G − Q such that all 2k endpoints of these paths are distinct. If we can apply one of the above extensions to each path P_{i}, then the resulting cycles C_{1}, …, C_{k} will be edge-disjoint outside of Q ∪ R.

Lemma 5 Let G be a graph with vertex partition V (G) = X ∪ Q ∪ R. Suppose that each of X ∪ R and Q ∪ R is a clique in G, and that d_{G}(x, Q) ≥ 1 for x ∈ X. Suppose further that X ∪ R can be partitioned into k pairs of which at most |R| − 1 are not Q-linked in G. Then G contains k Hamilton cycles which are edge-disjoint outside of Q ∪ R. Moreover, if |Q ∪ R| ≥ 2, then each of the Hamilton cycles contains an edge of G[Q ∪ R].

Proof. If |Q| = 1, then G = K_{2k+1}. Moreover, assumptions of the lemma imply that |R| ≥ k+1. Now we use Walecki’s decomposition with {0, 1, …, k} ⊆ R to obtain the required cycles.

We assume |Q| ≥ 2. Suppose that |R| ≤ ⌊\frac{k}{2}⌋ = ⌊\frac{|X∪R|}{4}⌋. We label the hypothesized pairs with {u_{i}, v_{i}}, 1 ≤ i ≤ k, in such a way that {u_{j}, v_{j}} is not Q-linked if and only if 1 ≤ j ≤ m, Figure 2: Using Extensions 1 and 2 to convert a u, v-path (shown in bold) into a Hamilton cycle of G[X ∪ Q ∪ R]. The vertices u and v may belong to either X or R.

for some m ≤ |R| − 1. Since Q ∪ R is a clique and d_{G}(x, Q) ≥ 1 for x ∈ X, it follows that, for 1 ≤ j ≤ m we have {u_{j}, v_{j}} ⊆ X and u_{j}, v_{j} have a common neighbour in Q. We apply Proposition 4 with H = G[X ∪ R] and S = R to obtain edge-disjoint Hamilton paths P_{1}, …, P_{k} in G[X ∪ R] where each P_{i} is a u_{i}, v_{i}-path and where each of P_{1}, P_{2}, …, P_{m} has an edge in G[R]. Since Q ∪ R is a clique, we may apply Extension 2 to P_{1}, …, P_{m} and apply Extension 1 to P_{m+1}, …, P_{k} to obtain k Hamilton cycles in G which are edge-disjoint outside of Q. See Figure 2. Each of these Hamilton cycles contains an edge of G[Q ∪ R], as required.

We now assume |R| ≥ ⌈\frac{k}{2}⌉. We partition X ∪ R into k pairs \{u_{i}, v_{i}\}, such that u_{i} ∈ R, 1 ≤ i ≤ k. By Proposition 4 (with S = ∅), the subgraph G[X ∪ R] contains k pairwise edgedisjoint Hamilton paths P_{i}, 1 ≤ i ≤ k, where each P_{i} is a u_{i}, v_{i}-path. Since Q ∪ R is a clique, d_{G}(x, Q) ≥ 1 for x ∈ X, and since |Q| ≥ 2, each pair {u_{i}, v_{i}} is Q-linked. Now we may use Extension 1 to extend each P_{i} to a Hamilton cycle in G. The resulting Hamilton cycles are edge-disjoint outside of Q ∪ R. Moreover, each cycle has an edge in G[Q ∪ R], as required.

3 Proof of Lemma 2

The basic idea used in the proof of Lemma 2 was introduced by Li [8] when he proved a weaker form of the lemma. Although our proof has details which are somewhat technical, the basic idea is not hard to describe. We first rearrange some edges of G = (X ∪ Y, E) using an operation called edge flipping. After performing a sequence of flips, we arrive at a new graph G_{s,t} to which we may apply Lemma 5, finding k Hamilton cycles which are edge-disjoint outside of Y. Finally, the flipped edges are restored one by one, while modifying the Hamilton cycles appropriately. In the end, we obtain k Hamilton cycles in G which are edge-disjoint outside of Y, as desired.

Let q, x, r ∈ V (G) be distinct vertices such that qx ∈ E(G) and xr ∉ E(G). We define a new graph G′ = G − qx + xr. We say that G′ has been obtained from G by flipping the ordered triple ⟨q, x, r⟩. We denote this operation by G ⟼^{qxr} G′. Suppose now that X ⊆ V (G) − {q, r}. We may perform the series of flips G ⟼^{qx_{1}r} G_{1} ⟼^{qx_{2}r} ⋯ ⟼^{qx_{p}r} G_{p} for any enumeration x_{1}, x_{2}, …, x_{p} of the set

X_{qr} = {x ∈ X : qx ∈ E(G), xr ∉ E(G)}.  (1)

The resulting graph G_{p} is independent of the ordering x_{1}, x_{2}, …, x_{p}. Therefore, the multiflip operation G ⟼^{qXr} G_{p} is well defined for the ordered triple ⟨q, X, r⟩. We note that the result of a multiflip operation may leave the graph unchanged.

Let X, Q and R be disjoint subsets of V (G). Let Q⃗ = (q_{1}, q_{2}, … q_{s}) and R⃗ = (r_{1}, r_{2}, …, r_{t}) be orderings (enumerations) of Q and R, respectively. The Q⃗XR⃗-flip sequence of G is the following sequence of multiflips, which is determined by the ordered triple ⟨Q⃗, X, R⃗⟩.

G ⟼^{q_{1}Xr_{1}} G_{1,1} ⟼^{q_{1}Xr_{2}} G_{1,2} ⟼^{q_{1}Xr_{3}} ⋯ ⟼^{q_{1}Xr_{t}} G_{1,t}

⟼^{q_{2}Xr_{1}} G_{2,1} ⟼^{q_{2}Xr_{2}} G_{2,2} ⟼^{q_{2}Xr_{3}} ⋯ ⟼^{q_{2}Xr_{t}} G_{2,t}

⋮

⟼^{q_{s}Xr_{1}} G_{s,1} ⟼^{q_{s}Xr_{2}} G_{s,2} ⟼^{q_{s}Xr_{3}} ⋯ ⟼^{q_{s}Xr_{t}} G_{s,t}.

A graph G_{i,j} in this sequence may be denoted by G_{i,j}[Q⃗XR⃗] when the context is not clear.

Let G = (X ∪ Y, E) be a graph of order at least 2k + 1, where G[X] and G[Y] are disjoint cliques, and where 1 ≤ |X| < 2k. We select a subset R of Y so that |X ∪ R| = 2k. We then select an ordering R⃗ of R and an ordering Q⃗ of Q = Y − R. Let s = |Q|, and let t = |R|. It is possible to make these selections in such a way that the graph G_{s,t}[Q⃗XR⃗] has a special linking property. A variation of the following result (where the connectivity condition is replaced by strong degree conditions) appears as Proposition 2 of [8].

Lemma 6 Let G = (X ∪Y, E) be a 2k-connected graph of order at least 2k +2, where G[X] and G[Y] are disjoint cliques, and where 1 ≤ |X| < 2k. Then there exist a subset R ⊆ Y having size t = 2k − |X|, an ordering R⃗ of R, and an ordering Q⃗ of Q = Y − R such that the set X ∪ R can be partitioned into k pairs of which at most t − 1 are not Q-linked in G_{s,t}[Q⃗XR⃗], where s = |Q|.

Proof. We first prove the lemma for k = 1. Suppose that X = {x}. By the 2-connectivity of G, there exist two vertices a, b ∈ N_{G}(x, Y). We select R = {a} and an arbitrary ordering Q⃗ of Q. We have G_{s,t}[Q⃗XR⃗] = G. Since |Q| ≥ 2, and since G[Y] is a clique, there is a vertex in Q − {b} which is adjacent to a. Therefore X ∪ R = {x, a} is a Q-linked pair in G_{s,t}.

We assume k ≥ 2. Suppose by way of contradiction that the lemma is false. Let k be the smallest integer such that there exists a 2k-connected counterexample G. We shall further suppose that G has as many edges as possible.

Claim 1 No vertex x ∈ X satisfies 2k + 1 ≤ d_{G}(x) ≤ |V (G)| − 2.

Suppose by way of contradiction that x ∈ X satisfies 2k + 1 ≤ d_{G}(x) ≤ |V (G)| − 2. Then x is not adjacent to some y ∈ Y. The graph G′ = G + xy together with the sets X and Y satisfy the hypothesis of the lemma. By the maximality of |E(G)|, there exist ordered sets R⃗, Q⃗, defining a Q⃗XR⃗-flip sequence on G′ such that X ∪R can be partitioned into k pairs {u_{i}, v_{i}} (i = 1, 2, …, k) of which at most t−1 are not Q-linked in G′_{s,t}[Q⃗XR⃗]. Consider now the graph G_{s,t} = G_{s,t}[Q⃗XR⃗] and the same partition {u_{i}, v_{i}} (i = 1, 2, …, k). Evidently G_{s,t} = G′_{s,t} − xy′ for some vertex y′ ∈ Q ∪ R. Without loss of generality, we suppose that x = u_{1}. For i = 2, 3, …, k, the pair {u_{i}, v_{i}} is Q-linked in G_{s,t} if and only if it is Q-linked in G′_{s,t}. If {u_{1}, v_{1}} is not Q-linked in G′_{s,t}, then we have proved the claim. Therefore we assume that {u_{1}, v_{1}} is Q-linked in G′_{s,t}. We show that {u_{1}, v_{1}} is also Q-linked in G_{s,t}. Since d_{G′_{s,t}}(u_{1}) = d_{G′}(u_{1}) ≥ 2k + 2, it follows that d_{G′_{s,t}}(u_{1}, Q) ≥ 3. Therefore d_{G_{s,t}}(u_{1}, Q) ≥ 2, so {u_{1}, v_{1}} is a Q-linked pair in G_{s,t}. Therefore G is not a counterexample, proving Claim 1.

Claim 2 Every vertex x ∈ X satisfies d_{G}(x) = 2k.

Suppose by way of contradiction that d_{G}(x) ≠ 2k for some x ∈ X. By Claim 1 and since G is 2k-connected, we have d_{G}(x) = |V (G)| − 1. Suppose 1 ≤ |X| ≤ 2. Then we define G_{s,t} = G_{s,t}[Q⃗XR⃗], where Q⃗, R⃗ are selected arbitrarily subject to Q ∪ R = Y, Q ∩ R = ∅, and |R| = t. Since |Q| ≥ 2, and Q ⊆ N_{G_{s,t}}(x, Q), and d_{G_{s,t}}(x′, Q) ≥ 1 for x′ ∈ X −{x}, any partition of X ∪ R into k pairs constitutes k Q-linked pairs in G_{s,t}, a contradiction.

We assume |X| ≥ 3. Let x′ ∈ X −{x}. Consider the graph G′ = G−{x, x′} and the partition (X′, Y) of V (G′), where X′ = X − {x, x′}. Then G′ is a 2(k − 1)-connected graph of order at least 2(k − 1) + 2, in which G′[X′] and G′[Y] are cliques, and where 1 ≤ |X′| < 2(k − 1). By choice of G, there exist ordered sets Q⃗, R⃗ and a partition of X′ ∪ R into k − 1 pairs {u_{i}, v_{i}} (1 ≤ i ≤ k − 1) of which at most t′ − 1 are not Q-linked in G′_{s,t′}[Q⃗X′R⃗]. (Here we have t′ = 2(k −1)−|X′| = t.) Consider the graph G_{s,t} = G_{s,t}[Q⃗XR⃗], and the partition of X ∪R given by {u_{1}, v_{1}}, {u_{2}, v_{2}}, …, {u_{k−1}, v_{k−1}}, {x, x′}. Obviously, for i = 1, 2, …, k − 1, the pair {u_{i}, v_{i}} is Q-linked in G_{s,t} if and only if it is Q-linked in G′_{s,t}. We have that d_{G_{s,t}}(x′) = d_{G}(x′) ≥ 2k > |X ∪ R − {x′}|, so d_{G_{s,t}}(x′, Q) ≥ 1. Since Q ⊆ N_{G_{s,t}}(x) and |Q| ≥ 2, the pair {x, x′} is Q-linked in G_{s,t}, a contradiction. This proves Claim 2.

Let us label the vertices in Y with r_{1}, r_{2}, …, r_{t}, q_{1}, q_{2}, …, q_{s} in such a way that

d_{G}(r_{1}, X) ≥ d_{G}(r_{2}, X) ≥ ⋯ ≥ d_{G}(r_{t}, X) ≥ d_{G}(q_{1}, X) ≥ d_{G}(q_{2}, X) ≥ ⋯ ≥ d_{G}(q_{s}, X).

Let R⃗ = r_{1}, r_{2}, …, r_{t} and Q⃗ = q_{1}, q_{2}, …, q_{s} be orderings of the sets R = {r_{1}, r_{2}, …, r_{t}} and Q = Y − R. We aim to show that the graph G_{s,t} = G_{s,t}[Q⃗XR⃗] satisfies the conclusion of Lemma 6 for some partition of X ∪ R into pairs.

Since |X ∪ R| = 2k, it follows from Claim 2 and the nature of the flipping procedure that X ∪ R is a clique in G_{s,t} and that

d_{G_{s,t}}(x, Q) = 1 for all x ∈ X.  (2)

Let S = {{u_{1}, v_{1}}, {u_{2}, v_{2}}, …, {u_{k}, v_{k}}} be a partition of X ∪ R into k pairs, such that the number, m, of pairs in S which are not Q-linked in G_{s,t} is minimized. We assume that {u_{j}, v_{j}} is not Q-linked if and only if 1 ≤ j ≤ m. Since G is a counterexample, we have 1 ≤ t ≤ m, so {u_{1}, v_{1}} is not Q-linked. Since Q ∪ R is a clique, |Q| ≥ 2, and by (2), we have u_{1}, v_{1} ∈ X and u_{1}, v_{1} have a common neighbour, say q_{i_{0}}, in Q. For 2 ≤ i ≤ k, none of the ways of re-pairing the four vertices u_{1}, v_{1}, u_{i}, v_{i} can result in more Q-linked pairs than S has. We apply this fact three times. First it follows that no pair in S is a subset of R. We may assume that u_{i} ∈ X, 1 ≤ i ≤ k. Second, by (2) (and an appropriate relabeling of vertices if needed) we may further assume N_{G_{s,t}}(u_{i}, Q) = {q_{i_{0}}} for 1 ≤ i ≤ k. Third, we find that for 1 ≤ j ≤ m, we have v_{j} ∈ X and N_{G_{s,t}}(v_{j}, Q) = {q_{i_{0}}}.

Let X′ = N_{G_{s,t}}(q_{i_{0}}, X). We have just shown that {u_{1}, …, u_{k}}∪{v_{1}, …, v_{m}} ⊆ X′. Therefore

|X′| ≥ k + m ≥ k + t.  (3)

Observing that d_{G}(q_{i_{0}}, X) ≥ d_{G_{s,t}}(q_{i_{0}}, X) = |X′|, we have by the choice of R⃗ and Q⃗ that

d_{G}(y, X) ≥ k + t, for y ∈ R ∪ {q_{1}, q_{2}, …, q_{i_{0}}}.  (4)

Let Q′ = { q_{i} ∈ Q : N_{G}(q_{i}, X′) ≠ ∅ }. We now show that

{q_{i_{0}}} ⊆ Q′ ⊆ {q_{1}, q_{2}, …, q_{i_{0}}}.  (5)

Indeed, suppose that q_{i} ∈ Q′ for some i > i_{0}. Then there exists x ∈ N_{G}(q_{i}, X′). In the Q⃗XR⃗-flip sequence of G, flips of the form ⟨q_{i_{0}}, x, r⟩ (where r ∈ R) are considered before flips of the form ⟨q_{i}, x, r⟩. Therefore q_{i_{0}}x ∈ E(G_{s,t}) implies q_{i}x ∈ E(G_{s,t}), which contradicts (2) and proves (5).

Claim 3 We have i_{0} = s.

In view of (5), it suffices to prove Q′ = Q. Suppose by way of contradiction that Q − Q′ ≠ ∅. Then (X − X′) ∪ R ∪ Q′ is a vertex cut in G separating the nonempty sets X′ and Q − Q′. By connectivity of G and by (3), we have 2k ≤ |X ∪ R| − |X′| + |Q′| ≤ 2k − (k + t) + |Q′|, so

|Q′| ≥ k + t ≥ 2 + t.

By (4), (5) and the above inequality we have

e_{G}(X, Y) ≥ e_{G}(X′, Q′ ∪ R) ≥ (k + t)((2 + t) + t) > 2k(t + 1).

On the other hand, using (2) and the fact X ∪ R is a clique in G_{s,t}, we get

e_{G}(X, Y) = e_{G_{s,t}}(X, Y) = |X|(t + 1) < 2k(t + 1).

This contradiction proves Claim 3.

By counting E_{G}(X, Y) in two ways we have, by choice of Q⃗ and R⃗, that

|X| (t + 1) ≥ |Y | d_{G}(q_{s}, X).  (6)

By (3) and Claim 3 we have d_{G}(q_{s}, X) ≥ k + t > 1 + t. Therefore |X| > |Y |. Alternatively, G is 2k-connected, so d_{G}(q_{s}, X) ≥ 2k − (|Y | − 1). Therefore (6) implies

(2k − t)(t + 1) ≥ (t + s)(2k − s − t + 1)
(s − 1)(s − 2k + 2t) ≥ 0

By the hypothesis, s − 1 > 0 so the second factor is non-negative. That is s + t ≥ 2k − t, which we may write as |Y | ≥ |X|. This contradicts |X| > |Y | and proves Lemma 6.

We now proceed to prove Lemma 2. Let G be a 2k-connected simple graph with V (G) = X ∪Y where X and Y are disjoint cliques in G. We say that G is happy if G contains k Hamilton cycles which are edge-disjoint outside of Y, and that either |Y | ≤ k or each of these Hamilton cycles contains an edge in G[Y].

If G has order at most 2k + 1, then by connectivity of G, we have G = K_{2k+1}, and G is happy by Proposition 3 (If |Y | ≥ k + 1, then we relabel vertices so that {0, 1, …, k} ⊆ Y).

We assume G has order at least 2k + 2. Suppose that Y = {y}. By connectivity we have |N(y, X)| ≥ 2k. We use Proposition 4 with H = G − y, S = ∅, and k arbitrary pairs in N(y, X), to find k Hamilton paths in G − y. These paths extend easily to k edge-disjoint Hamilton cycles in G, so G is happy.

Thus, we assume |Y | ≥ 2. Suppose |X| ≥ 2k. Let X′ = {u_{1}, v_{1}, u_{2}, v_{2}, …, u_{σ}, v_{σ}} be a maximal subset of X such that each pair {u_{i}, v_{i}} is Y -linked. If σ < k, then |X − X′| ≥ 2, and the graph G′ = G − X′ satisfies either d_{G′}(X − X′, Y) ≤ 1 or d_{G′}(Y, X − X′) ≤ 1. Therefore G has a cut of size at most |X′|+1 < 2k, a contradiction. Therefore σ ≥ k. We apply Proposition 4 with H = G[X], S = ∅, and pairs {u_{i}, v_{i}}, 1 ≤ i ≤ k, and then apply Extension 1 (with Q = Y) to the resulting paths to obtain k Hamilton cycles in G which are edge-disjoint outside of Y. The cycles produced by Extension 1 always have an edge in G[Y]. Therefore G is happy if |X| ≥ 2k.

We now assume that 1 ≤ |X| < 2k, |V (G)| ≥ 2k + 2, and thus |Y | ≥ 3. By Lemma 6 there exists a partition Y = Q ∪ R and orderings Q⃗, R⃗ such that X ∪ R can be partitioned into k pairs of which at most |R| − 1 are not Q-linked in G_{s,t} = G_{s,t}[Q⃗XR⃗], where s = |Q|, t = |R|. Since G has minimum degree at least 2k = |X ∪ R|, we have that X ∪ R is a clique in G_{s,t}, and for x ∈ X we have d_{G_{s,t}}(x, Q) ≥ 1. Therefore by Lemma 5, the graph G_{s,t} is happy.

It remains to show that if G′ ⟼^{qXr} G′′ is in the Q⃗XR⃗-flip sequence of G, and G′′ is happy, then G′ is happy. We assume that q ∈ Q, and r ∈ R are fixed and that X_{qr} ⊆ X is as in (1). We have

E(G′) − E(G′′) = {qx | x ∈ X_{qr}} and E(G′′) − E(G′) = {xr | x ∈ X_{qr}}.

Since Q ∪ R is a clique in both G′ and G′′, we have that, for b ∈ V (G′) − {r},

bq ∈ E(G′′) implies that bq, br ∈ E(G′) ∩ E(G′′).  (7)

Assume that G′′ is happy with Hamilton cycles C_{1}, …, C_{k}. Each C_{i} is the union of two r, qpaths, so there is a set P = {P_{1}, …, P_{2k}} of r, q-paths in G′′ which are edge-disjoint outside of Y, and a 2-to-1 function τ : P → {C_{1}, …, C_{k}} such that C_{k} = ⋃ τ^{−1}(C_{k}). (We do not further specify the function τ here, since we will soon be relabeling the paths in P.)

For 1 ≤ i ≤ 2k, let a_{i} be the neighbour of r in P_{i} and let b_{i} be the neighbour of q in P_{i}. We define an auxiliary directed graph H with V (H) = { P_{i} ∈ P | 1 ≤ i ≤ 2k and a_{i} ∈ X }, and ⟨P_{i}, P_{j}⟩ ∈ E(H) if and only if b_{i} = a_{j}. Since the paths are edge-disjoint outside of Y, at most one path in P can use any edge in the set { qa_{j}, qb_{j}, ra_{j}, rb_{j} | 1 ≤ j ≤ 2k and b_{j} ∈ X }. Therefore each vertex of H has in-degree and out-degree at most one. Thus each (weak) component of H is a directed path or cycle.

Let I ⊆ {1, …, 2k} be the set of indices i such that a_{i} ∈ X_{qr}. Let P_{I} = {P_{i} ∈ P | i ∈ I}, and consider the subgraph P = ⋃_{i=1}^{2k} P_{i} ⊆ G′′. Then E(P) − E(G′) = { a_{i}r | i ∈ I }, and every edge in this set is the first edge of exactly one path in P_{I}. This correspondence is bijective. For i ∈ I, we have qa_{i} ∈ E(G′) − E(G′′), so the vertex P_{i} ∈ V (H) has in-degree zero in H. Let H_{i} be the weak component of H such that P_{i} ∈ V (H_{i}). Then H_{i} is a directed path in H, whose initial vertex is P_{i}. We have shown that the edge a_{i}r ∈ E(P_{i}) is the only edge in the set ⋃{ E(P_{j}) | P_{j} ∈ V (H_{i}) } which does not belong to E(G′). Our plan is to modify the paths in V (H_{i}) so as to eliminate the edge a_{i}r from this set. After we have performed this modification for each i ∈ I, we shall have a new family of r, q-paths whose edges all belong to G′. We note that if I = ∅, then P ⊆ G′, so G′ is happy and there is nothing to prove.

After relabeling paths in P, we may assume that 1 ∈ I and H_{1} is the directed path P_{1}, P_{2}, …, P_{ℓ}. We have that a_{1} ∈ X_{qr} and b_{j} = a_{j+1} ∈ X − X_{qr}, j = 1, …, ℓ − 1. Since P_{ℓ} has out-degree zero in H, and since qb_{ℓ} ∈ E(P_{ℓ}) ⊆ E(G′′), we have by (7), that

b_{ℓ} ∈ Y or b_{ℓ}r ∈ E(G′) − E(P).  (8)

For j = 1, …, ℓ, we have P_{j} = ra_{j}R_{j}b_{j}q where R_{j} is an a_{j}, b_{j}-path in both G′′ and G′. The subgraph ⋃_{j=1}^{ℓ} P_{j} is illustrated in Figure 3 (a). For j = 1, …, ℓ, let P′_{j} = rb_{j}R′_{j}a_{j}q where R′_{j} is Figure 3: Diagram (a) shows ∪_{j=1}^{ℓ}P_{j}, and (b) shows ∪_{j=1}^{ℓ}P′_{j}. The paths P_{1} and P′_{1} are in bold. The subpaths R_{j} and R′_{j} are indicated as dashed lines, 1 ≤ j ≤ ℓ.

the reverse of the path R_{j}. The graph ⋃_{j=1}^{ℓ} P′_{j} is illustrated in Figure 3 (b). We have

E (⋃_{j=1}^{ℓ} P′_{j}) = E (⋃_{j=1}^{ℓ} P_{j}) ∪ {rb_{ℓ}, a_{1}q} − {ra_{1}, b_{ℓ}q}.  (9)

Since a_{1} ∈ X_{qr} and by (8), we have that ⋃_{j=1}^{ℓ} P′_{j} ⊆ G′. Since qa_{1} ∉ E(G′′), we have that a_{1} ≠ b_{i} for 1 ≤ i ≤ ℓ. It follows that the paths P′_{1}, …, P′_{ℓ} are edge-disjoint outside of Y.

For each i ∈ I and each P_{j} ∈ V (H_{i}) we define P′_{j} as we did in the case i = 1. We define P′_{m} = P_{m} for every P_{m} ∈ P − ⋃_{i∈I} V (H_{i}). For h = 1, …, k, we define C′_{h} = P′_{j} ∪ P′_{m}, where τ^{−1}(C_{h}) = {P_{j}, P_{m}}. (The function τ is defined near (7).) Since V (P′_{j}) = V (P_{j}) (j = 1, …, 2k), each C′_{h} is a Hamilton cycle in G′. Because the paths P′_{1}, …, P′_{k} are edge-disjoint outside of Y, the same is true for the cycles C′_{1}, …, C′_{k}. To conclude that G′ is happy, it suffices to show that if C_{h} contains an edge in G′′[Y], then C′_{h} contains an edge in G′[Y] (= G′′[Y]). Referring Figure 3, we see that every edge e ∈ E(C_{h}) − E(C′_{h}) has either has some vertex a_{j} ∈ X as an endpoint, or has b_{ℓ} as an endpoint. If b_{ℓ} ∈ X, then e is not a edge of G′′[Y]. If b_{ℓ} ∈ Y, then b_{ℓ}q is an edge of C′_{h} belonging to G′[Y]. Therefore G′ is happy, and Lemma 2 is proved.

4 Proof of Theorem 1

Suppose by way of contradiction that there exists a simple undirected graph G, a subset W ⊆ V (G), and an integer k such that the triple ⟨G, W, k⟩ satisfies the hypothesis, but not the conclusion of Theorem 1. We may assume that E(G[W]) is maximal. That is, for each pair of non-adjacent vertices u, v ∈ W, the graph G + uv either has k pairwise edge-disjoint cycles through W, or the triple ⟨G + uv, W, k⟩ does not satisfy the hypothesis of Theorem 1. Let

Y = \{ v ∈ W | d_{G}(v) ≥ \frac{n}{2} + 2(k − 1) \}.

Since G[W] is 2k-connected, we have |W | ≥ 2k + 1. By Proposition 3, G[W] is not complete, and hence Y ≠ ∅ by the hypothesis.

Figure 4: Two ways to eliminate the edge e = uv from C_{1} = P + e.

Claim 1 If G has k cycles through W which are edge-disjoint outside of Y, then

a) G has k pairwise edge-disjoint cycles through W.

b) If, moreover, for some uv ∈ E(G[Y]) d_{G}(u), d_{G}(v) ≥ \frac{n}{2} + 2k − 1, then G − uv has k pairwise edge-disjoint cycles through W.

Proof of part a). Let C_{1}, …, C_{k} be cycles through W in G which are edge-disjoint outside of Y, and such that

p = ∑_{1≤i<j≤k} |E(C_{i}) ∩ E(C_{j})|

is as small as possible. Suppose by way of contradiction that p > 0. Without loss of generality, there exists uv ∈ E(C_{1}) ∩ E(C_{2}) ⊆ E(G[Y]). Let P = C_{1} − uv, and let

G′ = (G − ⋃_{i=1}^{k} E(C_{i})) + E(P).

By definition of Y, and since uv ∈ E(C_{2}) we have

d_{G′}(u) + d_{G′}(v) ≥ d_{G}(u) + d_{G}(v) − 4(k − 1) + 2 ≥ n + 2.  (10)

It follows that either d_{G′}(u, V (P)) + d_{G′}(v, V (P)) ≥ |V (P)| + 2 or d_{G′}(u, V (G) − V (P)) + d_{G′}(v, V (G) − V (P)) ≥ n − |V (P)| + 1. In the former case, there exist consecutive vertices x, y along the u, v-path P such that uy, vx ∈ E(G′) ⊆ E(G), and we define D_{1} = C_{1} − {uv, xy} + {uy, vx} (see Figure 4 (a)). In the latter case, there exists z ∈ V (G) − V (P) such that uz, vz ∈ E(G), and we let D_{1} = C_{1} −{uv}+{uz, vz} (see Figure 4 (b)). In both cases, D_{1} is a cycle in G which goes through W. Let D_{i} = C_{i} for i = 2, …, k. Now D_{1}, …, D_{k} are cycles which satisfy the assumptions of the claim with ∑_{i≠j} |E(D_{i}) ∩ E(D_{j})| = p − 1, a contradiction. Therefore p = 0 and C_{1}, …, C_{k} are pairwise edge-disjoint cycles in G.

Proof of part b). Let uv ∈ E(G[Y]) so that d_{G}(u), d_{G}(v) ≥ \frac{n}{2} + 2k − 1. We may assume that all cycles are edge-disjoint by part a). Now, assume without loss of generality that uv ∈ E(C_{1}). We can repeat the above procedure except that now we cannot use the fact that uv ∈ E(C_{2}) to provide the term “+2” in (10). Instead we rely on the slightly stronger lower bound on d_{G}(u) and d_{G}(v) to recover inequality (10). Thus, we can modify C_{1} so that it will not contain the edge uv.

Claim 2 The graph G[Y] is complete.

Figure 5: Constructing the Hamilton cycle C_{j} of G[W] from the cycles D_{j} (in bold), and C_{i,j}, 1 ≤ i ≤ ω.

Suppose that xy ∉ E(G) for some x, y ∈ Y. Let G′ = G+xy. If u, v ∈ W satisfy dist_{G′[W]}(u, v) = 2 and dist_{G[W]}(u, v) ≠ 2, then either u or v belongs to {x, y} ⊆ Y. Therefore G′ satisfies the hypothesis of Theorem 1. By the choice of G, the graph G′ has k pairwise edge-disjoint cycles through W. Using Claim 1b, these cycles can be modified so that they avoid the edge xy. This contradicts that G is a counterexample, and proves Claim 2.

Let X = W − Y. By Claim 2, Proposition 3, and the fact that G is a counterexample, X ≠ ∅. Let G_{i} = (X_{i}, E_{i}), 1 ≤ i ≤ ω, be the connected components of G[X], for some ω ≥ 1. Let Y_{i} = N_{G}(X_{i}, Y), 1 ≤ i ≤ ω. By the definition of Y, no pair of vertices of X is at distance two in G[W]. Consequently, G_{i} is complete and Y_{i} ∩ Y_{j} = ∅ for 1 ≤ i < j ≤ ω. Let Y_{0} = Y − ∪_{i=1}^{ω}Y_{i}. Then W = X ∪ Y_{0} ∪ Y_{1} ∪ ⋯ ∪ Y_{ω}.

Claim 3 |Y_{i}| ≥ 2k, for i = 1, …, ω.

Suppose that |Y_{i}| < 2k for some 1 ≤ i ≤ ω. Since G[W] is 2k-connected, it follows that ω = 1 and Y = Y_{1}. Hence by Lemma 2, G[W] has k Hamilton cycles which are edge-disjoint outside of Y, and if |Y | ≥ k + 1, then each of them contains an edge in G[Y]. This, together with Claim 1a, contradicts that G is a counterexample.

Claim 4 The graph G[W] has k Hamilton cycles C_{1}, …, C_{k} which are edge-disjoint outside of Y.

Let i ∈ {1, …, ω}. Since G[W] is 2k-connected, and G[X_{i}], G[Y_{i}] are complete, and E_{G}(X_{i}, W − X_{i}) = E_{G}(X_{i}, Y_{i}), the graph G[X_{i} ∪ Y_{i}] is 2k-connected. By Claim 3, |Y_{i}| ≥ 2k ≥ k + 1, and by Lemma 2 the graph G[X_{i} ∪ Y_{i}] has k Hamilton cycles C_{i,1}, …, C_{i,k} which are edge-disjoint outside of Y_{i}, and such that each C_{i,j} (1 ≤ j ≤ k) contains an edge, say u_{i,j}v_{i,j} in G[Y_{i}].

Recall that W = X ∪ Y_{0} ∪ Y_{1} ∪ ⋯ ∪ Y_{ω}. For each j ∈ {1, …, k} we construct a Hamilton cycle C_{j} of G[W] as follows. The complete graph G[Y_{0} ∪_{i=1}^{ω} {u_{i,j}, v_{i,j}}] is either the single edge u_{1,j}v_{1,j}, or it has a Hamilton cycle D_{j} passing through all the edges in { u_{i,j}v_{i,j} | 1 ≤ i ≤ ω }. In the former case, we define C_{j} = C_{1,j}. In the latter case we obtain C_{j} from D_{j} by replacing each edge u_{i,j}v_{i,j} ∈ E(D_{j}) by the path C_{i,j} − u_{i,j}v_{i,j}, (1 ≤ i ≤ ω). See Figure 5. In either case, C_{j} is a Hamilton cycle of G[W]. Since the cycles C_{i,j} are edge-disjoint outside of Y, the same is true for the cycles C_{1}, …, C_{k}. This proves Claim 4.

Theorem 1 now follows from Claim 1a.

Remark 7 The cycles constructed in the proof of Theorem 1 use no edges in E(G − W). This is reflected in the fact that a triple ⟨G, W, k⟩ satisfies the hypothesis of Theorem 1 if and only if ⟨G − E(G − W), W, k⟩ satisfies the hypothesis of Theorem 1.

Acknowledgment We would like to thank two anonymous referees for their unusually careful reading of this manuscript.

References

[1] Béla Bollobás, Graham Brightwell, Cycles through specified vertices, Combinatorica 13 (1993), 147–155.

[2] Yoshimi Egawa, Edge-disjoint Hamiltonian cycles in graphs of Ore type, SUT J. Math. 29 (1993), 15–50.

[3] Genghua Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984), 221–227.

[4] R. J. Faudree, C. C. Rousseau, R. H. Schelp, Edge-disjoint Hamiltonian cycles, Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984), Wiley-Intersci. Publ., (1985), 231–249.

[5] Roland J. Gould, Updating the Hamiltonian problem–a survey, J. Graph Theory 15 (1991), 121–157.

[6] Roland J. Gould, Advances on the Hamiltonian problem—a survey, Graphs Combin. 19 (2003), 7–52.

[7] Hao Li, Edge disjoint cycles in graphs, J. Graph Theory 13 (1989), 313–322.

[8] Guojun Li, Edge disjoint Hamilton cycles in graphs, J. Graph Theory 35 (2000), 8–20.

[9] Guojun Li, Chuanping Chen, Disjoint Hamiltonian cycles in graphs, Australas. J. Combin. 19 (1999), 83–89.

[10] D. E. Lucas, Recreations mathematiques, Vol. II, Gauthiers Villars, Paris, 1892.

[11] C. St. J. A. Nash-Williams, Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, in “Studies in Pure Mathematics”, pp. 157–183, Academic Press, London, 1971.