\documentclass[11pt]{article} \setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in} \setlength{\topmargin}{0pt} \setlength{\headsep}{0pt} \setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt} \setlength{\evensidemargin}{0pt} \newtheorem{thm}{Theorem} \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{remark}[thm]{Remark} \newtheorem{claim}{\it Claim} \topmargin=1.5cm %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Environments, commands and packages \usepackage{amsmath} \usepackage{graphicx} \usepackage{color, rotating} \newenvironment{proof}% {\noindent{\bf Proof.}\ }{\hfill\rule{1ex}{1ex}\par\bigskip}% \newcommand{\dist}{\mathop{{\rm dist}}} \newcommand{\comment}[1]{\ $[\![${\scriptsize #1 }$]\!]$ \ } % used for comments \newcommand{\DEF}[1]{\emph{#1\/}} % used for definitions, eg. \DEF{flow} \newcommand{\flip}[1]{\overset {#1}{\longmapsto}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Structure of the front page \title{Edge Disjoint Cycles Through Specified Vertices} \author{Luis Goddyn\footnote{Research supported by the Natural Sciences and Engineering Research Council of Canada.}\\ Ladislav Stacho\footnote{Research supported by the Natural Sciences and Engineering Research Council of Canada.} \\ \small{ Department of Mathematics}\\[-0.8ex] \small{ Simon Fraser University, Burnaby, BC, Canada}\\[-0.8ex] \small \texttt{goddyn@math.sfu.ca, lstacho@math.sfu.ca} } %\date{\small Draft: \today\\ % \small Submitted: ???, 2003; Accepted: ???\\ % \small MR Subject Classifications: 05C38, (05C45, 05C40)} \begin{document} \maketitle \begin{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\'as/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]$. \end{abstract} \vspace{1ex} {\small \noindent Keywords: Hamilton cycle, Hamilton circuit, connectivity, prescribed vertices, Ore condition, Fan condition, packing cycles, long cycle. } %\comment{ I have not thought carefully here.} \section{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. % \begin{thm} \label{thm:main} Let $G=(V(G),E(G))$ be a finite undirected simple graph of order $n$, let $W \subseteq V(G)$, $|W|\ge 3$, and let $k$ be a positive integer. Suppose that %the induced subgraph $G[W]$ is $2k$-connected, and that %the vertex degrees satisfy \[ \max\{d_G(u), d_G(v)\} \ge n/2 + 2(k - 1) \] for every $u,v \in W$ such that $\dist_{G[W]}(u,v)=2$. Then $G$ contains $k$ pairwise edge-disjoint cycles $C_1, \ldots , C_k$ such that $W \subseteq V(C_i)$, $1\le i \le k$. \end{thm} %\comment{ I think that the requirements $W \ge 3$ % and that $G$ is simple are not necessary. % Do you agree?} % (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 \cite{Fan84}. This \emph{Fan-type} hypothesis gives a slightly stronger result than the corresponding \emph{Ore-type} condition (that $d_G(u) + d_G(v) \ge n+4(k-1)$ for $u, v \in W$, $uv \notin E$). In \cite{FRS85}, this degree condition was weakened (for sufficiently large $n$) to the best possible bound $d_G(u) + d_G(v) \ge n+2(k-1)$. Theorem \ref{thm:main} 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\'as and Brightwell \cite{BolBright93}. Their result is stated with the Ore-type degree hypothesis, %but does not require $2$-connectivity. which implies $2$-connectivity. % The special case $W=V$ is presented by Li \cite{Li00} in 2000 as a slight sharpening of Li and Chen \cite{LiChen99}. %%% ADDED BY LUIS A related line of research concerning the case $W=V$ is pursued in \cite{Egawa, Li89, NW}. They show that if $n \gg 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) \ge n$), and a minimum degree condition. %%% END OF ADDED BY LUIS Some of our techniques are borrowed from \cite{FRS85,Li00}. For further results on Hamilton cycles in graphs we refer the reader to \cite{G91,G03}. The proof of Theorem \ref{thm:main} proceeds in two steps. First we prove the following lemma, which we regard to be of equal importance to the main theorem. % \begin{lem} \label{lem:main} Let $G=(X \cup 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,\ldots,C_k$ such that $e \in E(C_i) \cap E(C_j)$ implies $e \in E(G[Y])$, for $1 \le i < j \le k$. Moreover if $|Y|\ge k+1$, then each $C_i$ contains an edge in $G[Y]$. \end{lem} % The special case $|Y|=1$ of Lemma \ref{lem:main} is (essentially) the well known decomposition of $K_{2k+1}$ into Hamilton cycles. % Our proof of Lemma \ref{lem:main} is inspired by Li's argument in \cite{Li00}. However, Li requires the additional hypothesis $|Y| \ge 2k$. Dropping Li's hypothesis results in significant complications. The proof of Lemma \ref{lem:main} is presented in Section~\ref{sec:lem}. The second step (Section~\ref{sec:thm}) is to derive Theorem~\ref{thm:main} from Lemma~\ref{lem:main}. %Theorem~\ref{thm:main} is best possible in two senses. %The following families of graphs show that %the theorem fails to hold if either the `local' degree condition %or the `global' connectivity condition is weakened. % %Let $k$ and $\omega$ be positive integers. %We construct $G = G(k,\omega)$ as follows. %Let $X_1,\ldots,X_\omega$ be complete graphs of order $2k-2$. %Let $Y_1,\ldots,Y_\omega$ be complete graphs of order $2k-1$. %Let $Z = \{z_1, \ldots, z_\omega\}$ be a stable set of vertices. %Let $V(G)$ be the disjoint union of %all the sets $X_i$, $Y_i$, and $Z$. %We add edges so that $Y_1 \cup \dots \cup Y_\omega$ is a clique in $G$. %For $i = 1,\ldots,\omega$, %we join every vertex in $Y_i$ to every vertex in $X_i\cup \{z_i\}$. %Let $W = X_1 \cup \dots \cup X_\omega \cup Y_1 \cup \dots \cup Y_\omega$. %Then $G$ has order $n=(4k-2)\omega$. %Every pair of vertices at distance $2$ in $G[W]$ has a vertex %$y \in Y_1 \cup \dots \cup Y_\omega$, %and $d_G(y) = (2k-2)+1 +( \omega(2k-1)-1)$, %which equals $n/2 + 2(k-1)$. %Thus $G$ satisfies Fan's condition. %However, the connectivity of $G$ is only $2k-1$ %($Y_1$ is a minimum vertex cut). %Oops. %\comment{ I do not see why G does not have $k$ edge-disjoint cycles through $W$.} %Let $G_1 \cong K_a$, $G_2 \cong K_b$ %be disjoint complete graphs with $a\le b$. %Let $U_1 \subset W_1 \subseteq K_a$ %satisfy $2k-1 = |U_1| < |W_1|$. %Let $G$ be obtained from $G_1 \cup G_2$ by adding all edges %between $U_1$ and $G_2$, and let $W=W_1 \cup V(G_2)$. %Then the Fan-type degree condition holds since each vertex %in $V(G_2)$ has degree at $b+2k-2 /ge n/2 + 2k -2$. \section{Notation and Auxiliary Results} \label{sec:aux} All graphs $G=(V(G),E(G))$ are simple graphs. Let $x, y \in V(G)$ and let $X,Y \subseteq 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)|$. %The subgraph of $G$ induced by $X$ is denoted $G[X]$. A $u,v$-path is a path whose endpoints are vertices $u$ and $v$. A cycle $C \subseteq G$ goes \DEF{through} $W$ if $W \subseteq V(C)$. %Let $G$ be a graph and Let $Q\subseteq V(G)$. A vertex pair $\{a,b\} \subseteq V(G)-Q$ is \DEF{$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 \emph{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$. \begin{figure}\label{fig:waleski} \begin{center} %\includegraphics[width=4cm]{fig2.pdf} \includegraphics[width=4cm]{fig2.eps} %\includegraphics*{fig2.pdf} %\includegraphics*{fig2.eps} \end{center} \caption{Walecki's decomposition: Rotate the depicted Hamilton cycle $k$ times.} \end{figure} In Figure \ref{fig:waleski}, we depict Walecki's famous decomposition of $K_{2k+1}$ into Hamilton cycles, as described by Lucas \cite{Luc}. % \begin{prop} \label{prop:Kn} For $\ell \ge 2k+1$, the graph $K_\ell$ contains $k$ pairwise edge-disjoint Hamilton cycles. \end{prop} % By deleting vertex $2k$ from Walecki's construction, we obtain a decomposition of $K_{2k}$ into $k$ Hamilton paths. Let $m \le \lfloor k/2 \rfloor$, and consider the $m$ Hamilton paths whose endpoints are the vertex pairs $\{1,2\}$, $\{3,4\}$, \ldots, $\{2m-1, 2m\}$. We observe that each of these Hamilton paths contains an edge joining $0$ to a vertex in the set $\{k+1, k+3, k+5,\ldots,k+2m-1\}$. By relabeling vertices appropriately, the following result follows easily. \begin{prop} \label{prop:path decomp} Let $H$ be a complete graph of order $n$. Let $u_1, v_1, u_2, v_2, \ldots, u_{k}, v_{k}$ be distinct vertices of $H$, where $k \le n/2$. Let $S \subseteq V(H)$ have cardinality $\:\ge m+1$, where $-1 \le m \le n/4$, and such that $u_j, v_j \not\in S$ for $j \le m$. Then $H$ has pairwise edge-disjoint Hamilton paths $P_1,\ldots,P_k$, where $P_i$ has endpoints $u_i$, $v_i$, $1 \le i \le k$, and where $P_j$ contains an edge with both endpoints in~$S$, $1 \le j \le m$. \end{prop} Let $Q,R,X$ be a partition of $V(G)$ so that $X$ and $Q\cup 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$. \begin{description} \item[Extension 1] \label{ext: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 \cup \{u,v\}]$. \item[Extension 2] \label{ext:2} Suppose $u, v$ have a common neighbour $q \in Q$, and that there exists $e=ab \in E(P)$ where $a,b\in 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\} \cup \{a,b\}]$. This construction makes sense even if $Q=\{q\}$. \end{description} Let $P_1, P_2, \ldots, 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, \ldots, C_k$ will be edge-disjoint outside of $Q\cup R$. \begin{lem} \label{lem:pairs to cycles} Let $G$ be a graph with vertex partition $V(G) = X \cup Q \cup R$. Suppose that each of $X\cup R$ and $Q\cup R$ is a clique in $G$, and that $d_G(x,Q)\ge 1$ for $x \in X$. Suppose further that $X\cup 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\cup R$. Moreover, if $|Q\cup R| \ge 2$, then each of the Hamilton cycles contains an edge of $G[Q\cup R]$. \end{lem} \begin{proof} If $|Q|=1$, then $G=K_{2k+1}$. Moreover, assumptions of the lemma imply that $|R|\ge k+1$. Now we use Walecki's decomposition with $\{0,1,\ldots,k\}\subseteq R$ to obtain the required cycles. We assume $|Q| \ge 2$. Suppose that $|R| \le \left\lfloor \frac{k}{2} \right\rfloor = \left\lfloor \frac{|X \cup R|}4\right\rfloor$. We label the hypothesized pairs with $\{u_i,v_i\}$, $1 \le i \le k$, in such a way that $\{u_j,v_j\}$ is not $Q$-linked if and only if $1 \le j \le m$, for some $m \le |R|-1$. Since $Q \cup R$ is a clique and $d_G(x,Q)\ge 1$ for $x \in X$, it follows that, for $1 \le j \le m$ we have $\{u_j, v_j\}\subseteq X$ and $u_j, v_j$ have a common neighbour in $Q$. We apply Proposition~\ref{prop:path decomp} with $H=G[X \cup R]$ and $S = R$ to obtain edge-disjoint Hamilton paths $P_1,\ldots,P_k$ in $G[X \cup R]$ where each $P_i$ is a $u_i,v_i$-path and where each of $P_1, P_2,\ldots,P_m$ %$P_j$ has an edge in $G[R]$ for $1 \le j \le m$. has an edge in $G[R]$. Since $Q\cup R$ is a clique, we may apply Extension~2 %\ref{ext:2} \comment{enumeration fails} to $P_1,\ldots,P_m$ and apply Extension~1 to $P_{m+1},\ldots,P_k$ to obtain $k$ Hamilton cycles in $G$ which are edge-disjoint outside of $Q$. See Figure~\ref{fig5}. Each of these Hamilton cycles contains an edge of $G[Q\cup R]$, as required. % \begin{figure} %\begin{center}\includegraphics[width=15cm]{fig5.pdf}\end{center} \begin{center}\includegraphics[width=15cm]{fig5.eps}\end{center} \caption{Using Extensions 1 and 2 to convert a $u,v$-path (shown in bold) into a Hamilton cycle of $G[X\cup Q \cup R ]$. The vertices $u$ and $v$ may belong to either $X$ or $R$. } \label{fig5} \end{figure} We now assume $|R| \ge \left\lceil \frac{k}{2} \right\rceil$. We partition $X \cup R$ into $k$ pairs $\{u_i,v_i\}$, such that $u_i \in R$, $1 \le i \le k$. By Proposition~\ref{prop:path decomp} (with $S=\emptyset$), the subgraph $G[X\cup R]$ contains $k$ pairwise edge-disjoint Hamilton paths $P_i$, $1 \le i \le k$, where each $P_i$ is a $u_i,v_i$-path. Since $Q \cup R$ is a clique, $d_G(x,Q)\ge 1$ for $x \in X$, and since $|Q|\ge2$, 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\cup R$. Moreover, each cycle has an edge in $G[Q\cup R]$, as required. \end{proof} %We shall use the following result, which appears as Proposition $2$ %in \cite{Li00}. %%\comment{Luis: We may not need this} %% %\begin{lem} %\label{lem:extensible_pairs} %Let $G$ be a graph, and let $X\cup Q\cup R$ be a partition of $V(G)$ %with $|X\cup R|=2k$ and $|Q|\ge 2$. %Suppose that $G[Q\cup R]$ is a clique, and that $d_{G}(x,Q)=1$ for every $x\in X$. %Suppose further that $d_{G}(p,X)\le k$ for all $q\in Q$. %Then $X\cup R$ can be partitioned into %%$k$ pairs $\{u_{1},v_{1}\},\{u_{2},v_{2}\},\ldots ,\{u_{k}v_{k}\}$ %%so that $d_{G}(\{u_{i},v_{i}\},Q)\ge 2$ for all $1\le i\le k$. %$k$ $Q$-linked pairs. %\end{lem} \section{Proof of Lemma \ref{lem:main}} \label{sec:lem} The basic idea used in the proof of Lemma~\ref{lem:main} was introduced by Li %\comment{...and someone else?} \cite{Li00} 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\cup Y, E)$ using an operation called \DEF{edge flipping}. After performing a sequence of flips, we arrive at a new graph $G_{s,t}$ to which we may apply Lemma \ref{lem:pairs to cycles}, 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 \in V(G)$ be distinct vertices such that $qx \in E(G)$ and $xr \notin E(G)$. We define a new graph $G' = G - qx + xr$. We say that $G'$ has been obtained from $G$ by \DEF{flipping} the ordered triple $\langle q,x,r\rangle$. We denote this operation by $G \flip{qxr} G'$. Suppose now that $X \subseteq V(G) - \{q,r\}$. We may perform the series of flips $G \flip{qx_1r} G_1 \flip{qx_2r} \cdots \flip{qx_pr} G_p$ for any enumeration $x_1, x_2, \ldots ,x_p$ of the set % \begin{equation} \label{eq:Xqr} X_{qr} = \{ x \in X : qx \in E(G), \, xr \notin E(G)\}. \end{equation} % The resulting graph $G_p$ is independent of the ordering $x_1, x_2, \ldots ,x_p$. Therefore, the \DEF{multiflip} operation $G \flip{qXr} G_p$ is well defined for the ordered triple $\langle q,X,r\rangle$. 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 $\vec{Q} = (q_1, q_2, \ldots q_s)$ and $\vec{R} = (r_1, r_2,\ldots, r_t)$ be orderings (enumerations) of $Q$ and $R$, respectively. The \DEF{$\vec QX\vec R$-flip sequence} of $G$ %defined by these two orderings is the following sequence of multiflips, which is determined by the ordered triple $\langle\vec Q, X, \vec R\rangle$. \begin{align*} G &\flip{q_1Xr_1} G_{1,1} \flip{q_1Xr_2} G_{1,2} \flip{q_1Xr_3} \cdots \flip{q_1Xr_t} G_{1,t} \\ &\flip{q_2Xr_1} G_{2,1} \flip{q_2Xr_2} G_{2,2} \flip{q_2Xr_3} \cdots \flip{q_2Xr_t} G_{2,t} \\ & \,\,\,\,\vdots \\ &\flip{q_sXr_1} G_{s,1} \flip{q_sXr_2} G_{s,2} \flip{q_sXr_3} \cdots \flip{q_sXr_t} G_{s,t}. \end{align*} % A graph $G_{i,j}$ in this sequence may be denoted by $G_{i,j}[\vec Q X \vec R]$ when the context is not clear. Let $G = (X \cup Y, E)$ be a graph of order at least $2k+1$, where $G[X]$ and $G[Y]$ are disjoint cliques, and where $1\le|X|<2k$. We select a subset $R$ of $Y$ so that $|X \cup R| = 2k$. We then select an ordering $\vec R$ of $R$ and an ordering $\vec 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}[\vec Q X \vec R]$ 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 \cite{Li00}. \begin{lem} \label{lem:good_pairs} Let $G=(X\cup 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 \le |X| < 2k$. Then there exist a subset $R \subseteq Y$ having size $t=2k-|X|$, an ordering $\vec R$ of $R$, and an ordering $\vec Q$ of $Q = Y-R$ such that the set $X \cup R$ can be partitioned into $k$ pairs of which at most $t-1$ are not $Q$-linked in $G_{s,t}[\vec Q X \vec R]$, where $s = |Q|$. \end{lem} \begin{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\in N_G(x,Y)$. We select $R=\{a\}$ and an arbitrary ordering $\vec Q$ of $Q$. We have $G_{s,t}[\vec Q X \vec R] = G$. Since $|Q|\ge 2$, and since $G[Y]$ is a clique, there is a vertex in $Q-\{b\}$ which is adjacent to $a$. Therefore $X \cup R = \{x,a\}$ is a $Q$-linked pair in $G_{s,t}$. We assume $k \ge 2$. Suppose by way of contradiction that the lemma is false. Let $k$ be the smallest integer %for which the lemma is not true, i.e. such that there exists a $2k$-connected counterexample $G$. We shall further suppose that $G$ has as many edges as possible. % \begin{claim} \label{claim:inter_degree} No vertex $x \in X$ satisfies $2k+1 \le d_G(x) \le |V(G)|-2$. \end{claim} % Suppose by way of contradiction that $x \in X$ satisfies $2k+1\le d_G(x) \le |V(G)|-2$. Then $x$ is not adjacent to some $y\in 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 $\vec R$, $\vec Q$, defining a $\vec QX\vec R$-flip sequence on $G'$ such that $X\cup R$ can be partitioned into $k$ pairs $\{u_{i},v_{i}\}$ ($i=1,2,\ldots ,k$) of which at most $t-1$ are not $Q$-linked in $G'_{s,t}[\vec Q X \vec R]$. Consider now the graph $G_{s,t} = G_{s,t}[\vec QX\vec R]$ and the same partition $\{u_{i},v_{i}\}$ ($i=1,2,\ldots ,k$). Evidently $G_{s,t} = G'_{s,t} - xy'$ for some vertex $y'\in Q\cup R$. Without loss of generality, we suppose that $x=u_{1}$. For $i=2,3,\ldots ,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 the degree of $u_{1}$ in $G'$ is at least $2k+2$, Since $d_{G'_{s,t}}(u_{1}) = d_{G'}(u_{1}) \ge 2k+2$, it follows that $d_{G'_{s,t}}(u_{1},Q)\ge 3$. Therefore $d_{G_{s,t}}(u_{1},Q)\ge 2$, so $\{u_{1},v_{1}\}$ is a $Q$-linked pair in~$G_{s,t}$. Therefore $G$ is not a counterexample, proving Claim~\ref{claim:inter_degree}. % % \begin{claim} \label{claim:max_degree} Every vertex $x \in X$ satisfies $d_G(x) = 2k$. \end{claim} Suppose by way of contradiction that $d_G(x) \ne 2k$ for some $x\in X$. By Claim \ref{claim:inter_degree} and since $G$ is $2k$-connected, %$x$ is adjacent to all other vertices in $G$. we have $d_G(x) = |V(G)|-1$. Suppose $1 \le |X|\le 2$. Then we define $G_{s,t} = G_{s,t}[\vec QX\vec R]$, where $\vec Q$, $\vec R$ are selected arbitrarily subject to $Q \cup R = Y$, $Q \cap R = \emptyset$, and $|R|=t$. Since $|Q|\ge 2$, and $Q \subseteq N_{G_{s,t}}(x,Q)$, and $d_{G_{s,t}}(x',Q)\ge 1$ for $x' \in X-\{x\}$, %and since $x$ is adjacent to all vertices in $Q$, any partition of $X\cup R$ into $k$ pairs constitutes $k$ $Q$-linked pairs in $G_{s,t}$, a contradiction. We assume $|X|\ge 3$. Let $x' \in 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\le |X'|<2(k-1)$. By choice of $G$, there exist ordered sets $\vec Q$, $\vec R$ and a partition of $X' \cup R$ into $k-1$ pairs $\{u_{i},v_{i}\}$ ($1\le i \le k-1$) of which at most $t'-1$ are not $Q$-linked in $G'_{s,t'}[\vec Q X' \vec R]$. (Here we have $t' = 2(k-1) - |X'| = t$.) Consider the graph $G_{s,t} = G_{s,t}[\vec Q X \vec R]$, and the partition of $X\cup R$ given by $\{u_{1},v_{1}\},\{u_{2},v_{2}\},\ldots ,\{u_{k-1},v_{k-1}\},\{x,x'\}$. Obviously, for $i=1,2,\ldots ,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') \ge 2k > |X\cup R -\{x'\}|$, so $d_{G_{s,t}}(x',Q)\ge 1$. Since $Q \subseteq N_{G_{s,t}}(x)$ and $|Q| \ge 2$, the pair $\{x,x'\}$ is $Q$-linked in $G_{s,t}$, a contradiction. This proves Claim~\ref{claim:max_degree}. \medskip Let us label the vertices in $Y$ with $r_1,r_2,\ldots ,r_t, q_1,q_2,\ldots ,q_s$ in such a way that \[ d_{G}(r_1,X)\ge d_{G}(r_2,X)\ge \cdots \ge d_{G}(r_t,X) \ge d_{G}(q_1,X)\ge d_{G}(q_2,X)\ge \cdots \ge d_{G}(q_s,X). \] Let $\vec R = r_1,r_2,\ldots, r_t$ and $\vec Q = q_{1},q_{2},\ldots ,q_{s}$ be orderings of the sets $R = \{r_1,r_2,\ldots, r_t\}$ and $Q = Y-R$. %The remainder of this proof is aimed at showing We aim to show that the graph $G_{s,t} = G_{s,t}[\vec Q X \vec R]$ satisfies the conclusion of Lemma~\ref{lem:good_pairs} for some partition of $X \cup R$ into pairs. % Since $|X \cup R| = 2k$, it follows from Claim \ref{claim:max_degree} and the nature of the flipping procedure that $X \cup R$ is a clique in $G_{s,t}$ and that % \begin{equation} \label{eq:degree_one} d_{G_{s,t}}(x,Q)=1\textrm{ for all }x\in X. \end{equation} % Let $S=\{\{u_{1},v_{1}\},\{u_{2},v_{2}\},\ldots ,\{u_{k},v_{k}\}\}$ be a partition of $X \cup 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 \le j \le m$. Since $G$ is a counterexample, we have $1 \le t \le m$, so $\{u_1,v_1\}$ is not $Q$-linked. Since $Q\cup R$ is a clique, $|Q|\ge 2$, and by~\eqref{eq:degree_one}, we have $u_1, v_1 \in X$ and $u_1,v_1$ have a common neighbour, say $q_{i_0}$, in $Q$. % For $2 \le i \le 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 \in X$, $1 \le i \le k$. Second, by~\eqref{eq:degree_one} (and an appropriate relabeling of vertices if needed) we may further assume $N_{G_{s,t}}(u_i,Q)=\{q_{i_0}\}$ for $1\le i\le k$. Third, we find that for $1 \le j \le m$, we have $v_j \in 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, \ldots, u_k\} \cup \{v_1,\ldots, v_m\} \subseteq X'$. Therefore % \begin{equation} \label{eq:m} |X'| %=d_{G_{s,t}}(q_{i_0},X) \ge k+m \ge k+t. \end{equation} % Observing that $d_{G}(q_{i_{0}},X)\ge d_{G_{s,t}}(q_{i_{0}},X) = |X'|$, we have by the choice of $\vec R$ and $\vec Q$ that % \begin{equation} \label{eq:degrees_in_Q} d_{G}(y,X) \ge k+t, \quad \text{for } y \in R \cup \{q_1,q_2,\ldots ,q_{i_{0}}\}. \end{equation} % Let $Q'=\{\,q_{i}\in Q\, :\, N_{G}(q_{i},X')\not =\emptyset \,\}$. We now show that % \begin{equation} \label{eq:Q'} \{q_{i_0}\} \subseteq Q' \subseteq \{q_1,q_2,\ldots ,q_{i_{0}}\}. \end{equation} % Indeed, suppose that $q_{i}\in Q'$ for some $i>i_{0}$. Then there exists $x\in N_G(q_i,X')$. In the $\vec QX\vec R$-flip sequence of $G$, flips of the form $\langle q_{i_0},x,r\rangle$ (where $r \in R$) are considered before flips of the form $\langle q_i,x,r\rangle$. Therefore $q_{i_0}x \in E(G_{s,t})$ implies $q_ix \in E(G_{s,t})$, which contradicts~\eqref{eq:degree_one} and proves~\eqref{eq:Q'}. % \begin{claim} \label{claim:wholeQ} We have % $Q'=Q$ and therefore $i_0 = s$. \end{claim} % In view of~\eqref{eq:Q'}, it suffices to prove $Q'=Q$. Suppose by way of contradiction that $Q-Q' \ne \emptyset$. Then $(X-X') \cup R\cup Q'$ is a vertex cut in $G$ separating the nonempty sets $X'$ and $Q-Q'$. By connectivity of $G$ and by~\eqref{eq:m}, we have $2k \le | X \cup R | -|X'| +|Q'| \le 2k -(k+t) + |Q'|$, so \[ |Q'| \ge k+t \ge 2+t. \] % By~\eqref{eq:degrees_in_Q},~\eqref{eq:Q'} and the above inequality we have \[ e_G(X,Y) \ge e_G(X',Q' \cup R) \ge (k+t) ((2+t)+t) > 2k(t+1). \] On the other hand, using~\eqref{eq:degree_one} and the fact $X \cup 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 \ref{claim:wholeQ}. \medskip By counting $E_G(X,Y)$ in two ways we have, by choice of $\vec Q$ and $\vec R$, that % \begin{equation} \label{eq:XYcount} |X|\,(t+1) \ge |Y|\,d_G(q_s,X). \end{equation} % By~\eqref{eq:m} and Claim~\ref{claim:wholeQ} we have $d_G(q_s,X) \ge k+t > 1+t$. Therefore $|X| > |Y|$. Alternatively, $G$ is $2k$-connected, so $d_G(q_s,X) \ge 2k-(|Y|-1)$. Therefore~\eqref{eq:XYcount} implies \[ (2k-t)(t+1) \ge (t+s)(2k-s-t+1) \] \[ (s-1)(s-2k+2t) \ge 0 \] By the hypothesis, $s-1>0$ so the second factor is non-negative. That is $s+t \ge 2k-t$, which we may write as $|Y| \ge |X|$. This contradicts $|X|>|Y|$ and proves Lemma~\ref{lem:good_pairs}. \end{proof} \medskip \setcounter{claim}{0} We now proceed to prove Lemma \ref{lem:main}. Let $G$ be a $2k$-connected simple graph with $V(G) = X\cup Y$ where $X$ and $Y$ are disjoint cliques in $G$. We say that $G$ is \emph{happy} if $G$ contains $k$ Hamilton cycles which are edge-disjoint outside of $Y$, and that either $|Y|\le 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~\ref{prop:Kn} (If $|Y|\ge k+1$, then we relabel vertices so that $\{0,1,\ldots,k\}\subseteq Y$). We assume $G$ has order at least $2k+2$. Suppose that $Y=\{y\}$. By connectivity we have $|N(y,X)| \ge 2k$. We use Proposition \ref{prop:path decomp} with $H=G-y$, $S = \emptyset$, 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|\ge 2$. Suppose $|X|\ge 2k$. Let $X'=\{u_1,v_1,u_2,v_2,\ldots,u_{\sigma},v_{\sigma}\}$ be a maximal subset of $X$ such that each pair $\{u_i,v_i\}$ is $Y$-linked. If $\sigma0$. Without loss of generality, there exists $uv\in E(C_{1})\cap E(C_{2})\subseteq E(G[Y])$. Let $P=C_{1}-uv$, and let \[ G'=\left(G-\bigcup _{i=1}^{k}E(C_{i})\right)+E(P). \] By definition of $Y$, and since $uv \in E(C_2)$ we have \begin{equation}\label{oh} d_{G'}(u)+d_{G'}(v)\ge d_G(u)+d_G(v)-4(k-1)+2\ge n+2. \end{equation} % \begin{figure} \begin{center}\includegraphics[width=15cm]{fig4.eps}\end{center} \caption{Two ways to eliminate the edge $e=uv$ from $C_1 = P+e$. } \label{fig4} \end{figure} % It follows that either $d_{G'}(u,V(P))+d_{G'}(v,V(P))\ge |V(P)|+2$ or $d_{G'}(u,V(G)-V(P))+d_{G'}(v,V(G)-V(P))\ge n-|V(P)|+1$. In the former case, there exist consecutive vertices $x,y$ along the $u,v$-path $P$ such that $uy,vx\in E(G')\subseteq E(G)$, and we define $D_1=C_1-\{uv,xy\}+\{uy,vx\}$ (see Figure~\ref{fig4} (a)). % In the latter case, there exists $z\in V(G)-V(P)$ such that $uz,vz\in E(G)$, and we let $D_1=C_1-\{uv\}+\{uz,vz\}$ (see Figure~\ref{fig4} (b)). In both cases, $D_1$ is a cycle in $G$ which goes through $W$. Let $D_i=C_i$ for $i=2,\ldots ,k$. Now $D_1, \dots, D_k$ are cycles which satisfy the assumptions of the claim with $\sum _{i\not =j}|E(D_i)\cap E(D_j)|=p-1$, a contradiction. Therefore $p=0$ and $C_1,\dots,C_k$ are pairwise edge-disjoint cycles in $G$. {\it Proof of part b).} Let $uv\in E(G[Y])$ so that $d_G(u),\,d_G(v)\ge \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\in E(C_1)$. We can repeat the above procedure except that now we cannot use the fact that $uv\in E(C_2)$ to provide the term ``+2'' in \eqref{oh}. Instead we rely on the slightly stronger lower bound on $d_G(u)$ and $d_G(v)$ to recover inequality \eqref{oh}. %in (\ref{oh}) has to be guaranteed by the stronger lower bound on degrees of $u$ and $v$. Thus, we can modify $C_{1}$ so that it will not contain the edge $uv$. \begin{claim} \label{claim:G[Y]complet} The graph $G[Y]$ is complete. \end{claim} % Suppose that $xy\notin E(G)$ for some $x,y\in Y$. Let $G'=G+xy$. If $u,v\in W$ satisfy $\dist_{G'[W]}(u,v)=2$ and $\dist_{G[W]}(u,v)\ne2$, then either $u$ or $v$ belongs to $\{x,y\} \subseteq Y$. Therefore $G'$ satisfies the hypothesis of Theorem~\ref{thm:main}. %Since $x,y\in Y$, the graph $G'=G+uv$ satisfies the assumptions of the theorem. %\comment{I am expanding on this} By the choice of $G$, the graph $G'$ has $k$ pairwise edge-disjoint cycles through~$W$. Using Claim \ref{claim:edc}b, these cycles can be modified so that they avoid the edge $xy$. This contradicts that $G$ is a counterexample, and proves Claim~\ref{claim:G[Y]complet}. \vspace{2mm} Let $X=W-Y$. By Claim \ref{claim:G[Y]complet}, Proposition \ref{prop:Kn}, and the fact that $G$ is a counterexample, $X\not =\emptyset $. Let $G_i=(X_i,E_i)$, $1\le i\le \omega $, be the connected components of $G[X]$, for some $\omega \ge 1$. Let $Y_i=N_{G}(X_i,Y)$, $1\le i\le \omega $. 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\cap Y_j=\emptyset$ for $1 \le i < j \le \omega$. Let $Y_{0}=Y-\cup _{i=1}^{\omega }Y_{i}$. Then $W = X \cup Y_0 \cup Y_1 \cup \dots \cup Y_\omega$. %\begin{equation} %\begin{array}{l} %G_{i},\, \, 1\le i\le \omega ,\textrm{ is complete},\\ %Y_{i}\cap Y_{j}=\emptyset ,\textrm{ for }i\not =j.\end{array} %\end{equation} \begin{claim}\label{cl:2k} \label{claim:yi>}$|Y_{i}|\ge 2k$, for $i=1,\ldots ,\omega $. \end{claim} Suppose that $|Y_{i}|<2k$ for some $1\le i\le \omega $. Since $G[W]$ is $2k$-connected, it follows that $\omega =1$ and $Y=Y_1$. Hence by Lemma~\ref{lem:main}, $G[W]$ has $k$ Hamilton cycles which are edge-disjoint outside of~$Y$, and if $|Y|\ge k+1$, then each of them contains an edge in $G[Y]$. This, together with Claim~\ref{claim:edc}a, contradicts that $G$ is a counterexample. \begin{claim} \label{claim:G[W] cycles} The graph $G[W]$ has $k$ Hamilton cycles $C_{1},\dots ,C_{k}$ %such that $E(C_{i})\cap E(C_{j})\subseteq E(G[Y])$ for $i\not =j$. which are edge-disjoint outside of~$Y$. \end{claim} % Let $i\in\{1,\dots,\omega\}$. 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\cup Y_i]$ is $2k$-connected. By Claim \ref{cl:2k}, $|Y_i| \ge 2k\ge k+1$, and by Lemma~\ref{lem:main} the graph $G[X_i\cup Y_i]$ has $k$ Hamilton cycles $C_{i,1},\dots,C_{i,k}$ which are edge-disjoint outside of $Y_i$, and such that each $C_{i,j}$ ($1 \le j \le k$) contains an edge, say $u_{i,j} v_{i,j}$ in $G[Y_i]$. Recall that $W = X \cup Y_0 \cup Y_1 \cup \dots \cup Y_\omega$. For each $j\in \{1,\ldots,k\}$ we construct a Hamilton cycle $C_j$ of $G[W]$ as follows. The complete graph $G[Y_{0}\cup _{i=1}^{\omega }\{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}\, \mid \, 1\le i\le \omega \,\}$. 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} \in E(D_j)$ by the path $C_{i,j}-u_{i,j}v_{i,j}$, ($1\le i\le \omega $). See Figure~\ref{fig3}. 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,\dots,C_k$. This proves Claim~\ref{claim:G[W] cycles}. % \begin{figure} %\begin{center}\includegraphics[width=7cm]{fig3.pdf}\end{center} \begin{center}\includegraphics[width=7cm]{fig3.eps}\end{center} \caption{Constructing the Hamilton cycle $C_j$ of $G[W]$ from the cycles $D_j$ (in bold), and $C_{i,j}$, $1 \le i \le \omega$. } \label{fig3} \end{figure} % Theorem~\ref{thm:main} now follows from Claim \ref{claim:edc}a. \hfill\rule{1ex}{1ex}\par\bigskip \begin{remark} {\rm The cycles constructed in the proof of Theorem~\ref{thm:main} use no edges in $E(G-W)$. This is reflected in the fact that a triple $\langle G,W,k \rangle$ satisfies the hypothesis of Theorem~\ref{thm:main} if and only if $\langle G-E(G-W),W,k \rangle$ satisfies the hypothesis of Theorem~\ref{thm:main}. } \end{remark} \noindent \textbf{Acknowledgment} We would like to thank two anonymous referees for their unusually careful reading of this manuscript. %\newpage %\bibliographystyle{abbrv} \begin{thebibliography}{99} \bibitem{BolBright93} B\'ela Bollob\'as, Graham Brightwell, Cycles through specified vertices, \textit{Combinatorica} \textbf{13} (1993), 147--155. \bibitem{Egawa} Yoshimi Egawa, Edge-disjoint Hamiltonian cycles in graphs of Ore type, {\it SUT J.~Math.}~{\bf 29} (1993), 15--50. \bibitem{Fan84} Genghua Fan, New sufficient conditions for cycles in graphs, \textit{J.~Combin. Theory Ser.~B} \textbf{37} (1984), 221--227. \bibitem{FRS85} R. J. Faudree, C. C. Rousseau, R. H. Schelp, Edge-disjoint Hamiltonian cycles, \textit{Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984)}, Wiley-Intersci. Publ., (1985), 231--249. \bibitem{G91} Roland J. Gould, Updating the Hamiltonian problem--a survey, \textit{J.~Graph Theory} \textbf{15} (1991), 121--157. \bibitem{G03} Roland J. Gould, Advances on the Hamiltonian problem---a survey, \textit{Graphs Combin.} \textbf{19} (2003), 7--52. \bibitem{Li89} Hao~Li, Edge disjoint cycles in graphs, {\it J.~Graph Theory} {\bf 13} (1989), 313--322. \bibitem{Li00} Guojun Li, Edge disjoint Hamilton cycles in graphs, \textit{J.~Graph Theory} \textbf{35} (2000), 8--20. \bibitem{LiChen99} Guojun Li, Chuanping Chen, Disjoint Hamiltonian cycles in graphs, \textit{Australas. J.~Combin.} \textbf{19} (1999), 83--89. \bibitem{Luc} D.~E.~Lucas, Recreations mathematiques, Vol.~II, Gauthiers Villars, Paris, 1892. \bibitem{NW} C.~St.~J.~A.~Nash-Williams, Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, {\it in} ``Studies in Pure Mathematics'', pp.~157--183, Academic Press, London, 1971. \end{thebibliography} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \theoremstyle{remark} \newtheorem{claim}{Claim} \theoremstyle{plain} \newtheorem{lem}{Lemma} \theoremstyle{remark} \newtheorem{note}{Note} \theoremstyle{plain} \newtheorem{prop}{Proposition} \theoremstyle{plain} \newtheorem{thm}{Theorem}