%        A LaTex file for a 9 page document
%
%
\documentstyle[12pt]{article}
\textheight = 9in
\textwidth = 6in
\topmargin = -\headheight
\pagestyle{myheadings} 
\markright{\sc the electronic journal of combinatorics 6 (1999), \#R4\hfill} 
\thispagestyle{empty} 


\newtheorem{th}{Theorem}
	\renewcommand{\theth}{\arabic{th}}
\newtheorem{lm}[th]{Lemma}
\newtheorem{cor}[th]{Corollary}
\newtheorem{pro}[th]{Proposition}
\newtheorem{remark}[th]{Remark}

\newtheorem{oldth}{Theorem}
	\renewcommand{\theoldth}{\Alph{oldth}}

\newtheorem{conj}[oldth]{Conjecture}

\title{A $[k,\,k+1]$-Factor Containing A Given Hamiltonian Cycle}

\author{
 Cai Mao-cheng \thanks{ Research supported partially by
the exchange program between Chinese Academy of Sciences and Japan Society
for Promotion of Sciences and by National Natural Science Foundation of
China.} \hspace{1em} Yanjun Li 
\vspace{1ex}\\Institute of Systems
Science\vspace{1ex}\\Chinese Academy of Sciences,\ Beijing \ 100080,\
 P.R. China
\vspace{1ex}\\ \quad\ {\small\texttt{caimc@bamboo.iss.ac.cn}}\ \quad \  
{\small\texttt{cogt@bamboo.iss.ac.cn}}
\vspace{1ex}\\Mikio Kano \vspace{1ex}\\Department of Computer and
Information Sciences \\Ibaraki University,\ \ Hitachi \ 316, \ Japan
\vspace{1ex}\\
{\small\texttt{kano@cis.ibaraki.ac.jp}}
}
\date{}

\begin{document}


\maketitle
\begin{abstract}
We prove the following best possible result.
Let $k\ge 2\/$ be an integer
and $G\/$ be a graph of order $n\/$ with minimum degree at least $k$.
Assume $n \ge 8k-16\/$ for even $n\/$ and $n \ge 6k-13\/$ for odd $n\/$.
If the degree sum of each pair of nonadjacent vertices of $G\/$ is at
least $n$,
then for any given Hamiltonian cycle $C\/$ of $G\/$,
$G\/$ has a $[k,\:k+1]$-factor
containing $C\/$.
\end{abstract}

\smallskip
\centerline{{\small Submitted: December 15, 1997; Accepted: November 27,
1998.}}
\vspace{1cm}

MR Subject Number: {05C75}\hfill

Keywords: $[k,\,k+1]$-factor, Hamiltonian cycle, degree condition\hfill



\bigskip


\thispagestyle{empty} 
\section{Introduction}
All graphs under  consideration are undirected, finite and simple.
A graph $G\/$ consists of a non-empty set $V(G)\/$ of vertices
and a set $E(G)\/$ of edges.
For two vertices $x\/$ and $y\/$ of $G$,
let $xy\/$ and $yx\/$ denote an edge joining  $x\/$ to $y\/$.
Let $X\/$ be a subset of $V(G)\/$.
We write $G[X]\/$ for the
subgraph of $G\/$ induced by $X\/$, and define
$\overline{X}:=V(G)\setminus X\/$.
The subset $X\/$ is said to be {\em independent \/} if no two vertices
of $X\/$ are adjacent in $G$.
Sometimes $x\/$ is used for a singleton $\{x\}\/$.
For a vertex $x\/$ of $G\/$,
we denote by $d_G(x)\/$  the degree of $x\/$ in
$G\/$, that is, the number of edges of $G\/$ incident with $x\/$.
We denote by $\delta (G)$ the minimum degree of $G$.
For integers $a\/$ and $b$, $0\ \leq a \leq b \/$,
an {\em $[a,\:b]$-factor} of $G\/$ is defined to be a
spanning subgraph $F\/$ of $G\/$ such that
$$
a \leq d_F(x) \leq b \quad\mbox{for all }\, x\in V(G)\/,
$$
\noindent and an $[a,\:a]$-factor is abbreviated to an {\em $a$-factor}.
A subset $M\/$ of $E(G)\/$ is called a {\em matching} if no two edges of
$M\/$ are adjacent in $G\/$.
For two graphs $H\/$ and $K$,
the {\em union} $H \cup K\/$ is the graph with vertex set $V(H) \cup
V(K)\/$ and
edge set $E(H) \cup E(K)\/$,
and the {\em join} $H+K\/$ is the graph with vertex set $V(H) \cup V(K)\/$
and edge set
$E(H) \cup E(K) \cup \{xy~|~ x \in V(H) ~~ \mbox{and}~~ y \in V(K)\}$.
Other notation and definitions not defined here can be found in \cite{bm}.

We first mention some known results concerning our theorem.


\begin{oldth}[\cite{ore}]
\quad Let $G\/$ be a graph of order $n \geq 3$.
If the degree sum of each pair of nonadjacent
vertices is at least $n$,
then $G\/$ has a Hamilton cycle.
\label{oldth:ore}
\end{oldth}

\begin{oldth}[\cite{in}]
\quad Let $k\/$ be a positive integer and $G\/$ be a graph of order $n$
with $n\ge 4k-5,\; kn\/$ even, and $\delta (G) \geq k$.
If the degree sum of each pair of nonadjacent
vertices is at least $n$,
then $G\/$ has a $k$-factor.
\label{oldth:in}
\end{oldth}

Combining the above two theorems,
we can say that if a graph $G\/$ satisfies the conditions in
Theorem~\ref{oldth:in},
then $G\/$ has a Hamilton cycle $C\/$ together with
a connected $[k,\: k+2\/]$-factor containing $C$,
which is the union of $C\/$ and a $k$-factor of $G\/$ \cite{kan}.

\begin{oldth}[\cite{ni}]
\quad Let $k\ge 3\/$ be an integer and $G\/$ be a connected graph
of order $n$ with $n\ge 4k-3,\; kn$\ even, and $\delta (G) \geq k$.
If for each pair $(x,y)$ of nonadjacent vertices of $V(G)$,
$$
\max\{d_G(x),\, d_G(y)\}\ge \frac{n}{2}\,,
$$
\noindent then $G$ has a $k$-factor.
\end{oldth}


\begin{oldth}[\cite{cai}]
\quad Let $k \geq 3$ be an odd integer and $G$ be a connected graph of
odd order $n$ with $n \ge 4k-3$, and $\delta (G) \geq k$.
If for each pair $(x,y)$ of nonadjacent vertices of $G$,
$$
\max\{d_G(x),\ d_G(y) \} \ge \frac{n}{2}\,,
$$
\noindent then $G\/$ has  a connected $[k,\:k+1]$-factor.
\label{oldth:Ca}
\end{oldth}

\begin{oldth}[\cite{ca}]
\quad Let $G$ be a connected graph of order $n$, let $f$ and $g$ be two 
positive integer functions defined on $V(G)$ which satisfy $2 \leq f(v)
\leq g(v)$ for each vertex 
$v \in V(G)$. Let $G$ have an $[f,g]$-factor $F$ and put $\mu = min
\{f(v):\ v \in V(G)\}$. Suppose 
that among any three independent vertices of $G$ there are (at least)
two vertices with degree sum at 
least $n - \mu$. Then $G$ has a matching $M$ such that $M$ and $F$ are
edge-disjoint and $M+F$ is a 
connected $[f,g+1]$-factor of $G$.
\end{oldth}


\bigskip
The purpose of this paper is to extend ``connected $[k,\:k+1]$-factor''
in some of the above theorems to
``$[k,\:k+1]$-factor containing a given Hamiltonian cycle'',
which is obviously a 2-connected $[k,\:k+1]$-factor.

Our main result is the following

\begin{th}
Let $k \ge 2$ be an integer and $G$ be a graph of order $n\ge 3$ with
$\delta (G) \geq k$.
Assume $n \ge 8k-16$ for even $n$ and $n \ge 6k-13$
for odd $n$.
If for each pair $(x,y)$ of nonadjacent vertices of $G$,
\begin{equation}
d_G(x) + d_G(y) \ge n,
\label{eq:1}
\end{equation}
then for any given Hamiltonian cycle $C$, $G$ has a $[k,\:k+1]$-factor
containing $C$.
\label{th:clk}
\end{th}


\bigskip
Now we conclude this section with a new result concerning our theorem.

\begin{oldth}{\rm \cite{wz}}
\quad Let $k\ge 2\/$ be an integer and $G\/$ be a connected graph of
order $n\/$ such that
$n\ge 8k-4,\;kn\/$ is even and $\delta (G) \geq n/2$.
Then $G\/$ has a
$k$-factor containing a Hamiltonian cycle.
\end{oldth}

For a graph $G\/$ of order $n$, the condition $\delta (G) \geq n/2\/$ does not
 guarantee the existence of a $k$-factor which contains a given
Hamiltonian cycle of $G$.
Let $n \ge 5\/$ and $k \ge 3\/$ be integers,
and set
$$
m=\left\{
\begin{array}{ll}
\frac{n}{2}+2 & \quad \mbox{ for even $n$,}\\
\frac{n+3}{2} & \quad \mbox{ for odd $n$.}
\end{array}
\right.
$$
Let $C_m=(v_1v_2 \ldots v_m)\/$ be a cycle of order $m\/$ and
$P_{n-m}= (v_{m+1}v_{m+2} \ldots v_n)\/$ a path of order $n-m$.
Then the join $G:=C_m + P_{n-m}$
has no $k$-factor containing the Hamiltonian cycle $(v_1v_2 \ldots v_n)$
but satisfies $\delta (G) \ge n/2$.

\section{Proof}
Our proof depends on the following theorem,
which is a special case of Lov\'{a}sz's $(g,f)$-factor theorem
\cite{lo}(\cite{tutte}).

\begin{th}
Let $G\/$ be a graph and $a\/$ and $b\/$ be integers such that  $1 \leq a <b$.
Then $G\/$ has an $[a,b]$-factor if and only if
$$ \gamma (S,T):=b|S|  - a|T| + \sum _{x\in T} d_{G-S}(x) \geq 0 $$
for all disjoint subsets $S,~T \subseteq V(G)$.
\label{th:lo}
\end{th}

{\bf Proof of Theorem~\ref{th:clk} }
 ~~We may assume $k \geq 3\/$ since $G\/$ has $C\/$ for $k=2$.
Let
$$ H:=G-E(C), ~~ U:=\{x \in V(G) ~|~  d_G(x) \geq \frac{n}{2}\},
~~W:=V(G) \setminus U, ~~ \rho :=k-2. $$
Then $V(H)=V(G)$, $ \rho  \geq 1$,
$$d_H(x)=d_G(x)-2 \geq \rho ~~~~  \mbox{for all}~~~ x \in V(H),$$
$n \geq 8\rho \/$ for even $n\/$ and $n \geq 6\rho -1\/$ for odd $n$.
Moreover the induced subgraph $G[W]\/$ is a complete graph since $d_G(x)
+ d_G(y) <n\/$ for any two vertices $x\/$ and $y\/$ of $W$.

Obviously, $G\/$ has a required factor if and only if $H\/$ has a $[\rho
,\rho +1]$-factor.
Suppose, to the contrary, that $H\/$ has no such factor.
Then, by Theorem~\ref{th:lo}, there exist disjoint subsets $S\/$ and
$T\/$ of $V(H)\/$ such that
\begin{equation}
 \gamma (S,T) = (\rho +1)s - \rho t + \sum _{x\in T} d_{H-S}(x) < 0 .
\label{eq:a2}
\end{equation}
where $t=|T|\/$ and $s=|S|$.

If $d_{H-S}(v) \geq \rho \/$ for some $v \in T$,
then $ \gamma (S,T) \geq \gamma (S,T\setminus \{v\})$, and thus
(\ref{eq:a2}) is still holds for $S\/$ and $T\setminus \{v\}$.
Thus we may assume that
\begin{equation}
d_{H-S}(x) \leq \rho  -1  ~~~~~ \mbox{for all} ~~~~ x \in T.
\label{eq:a3}
\end{equation}

If $S= \emptyset$,
then $ \gamma (\emptyset, T)= -\rho t + \sum _{x\in T} d_{H}(x) \geq
0\/$ as  $d_H(x) \geq \rho \/$ for all $x \in V(H)$.
Thus
\begin{equation}
s \geq 1 .
\label{eq:b2}
\end{equation}

If $t \leq \rho +1$, then we have
\begin{eqnarray*}
\gamma(S,T) & \geq & (\rho +1)s - \rho t + \sum_{x \in T}(d_H(x) -s) \\
 	& \geq & (\rho +1)s - \rho t +t(\rho -s) \\
	& = & s(\rho +1-t) \geq 0.
\end{eqnarray*}
This contradicts (\ref{eq:a2}).
Hence
 \begin{equation}
t \geq \rho +2.
\label{eq:b3}
\end{equation}

We now prove the next Claim:

\bigskip
{\bf Claim~1.} ~~
{\em $ s \leq \frac{n}{2}-3$ ~~if $n\/$ is even, ~and ~~ $ s \leq
\frac{n-5}{2}$ ~~if $n\/$ is odd.}

\bigskip
Assume that $n\/$ is even and $s \geq (n/2) - 2$.
Let $q:=s-(n/2)+2 \geq 0\/$ and $r:=n-s-t \geq 0$.
Then it follows from $\rho  \geq 1\/$ and $n \geq 8 \rho \/$ that
\begin{eqnarray*}
 \gamma (S,T) & = & (\rho +1)q+\rho (r+q) + \sum_{x\in T} d_{H-S}(x) +
\frac{n}{2}-4\rho -2  \\
	& \geq &  2q + r+q + \sum_{x\in T} d_{H-S}(x) -2.
\end{eqnarray*}
Hence we may assume  $q=0\/$ and $r \leq 1\/$ since otherwise $\gamma
(S,T) \geq 0$.
If $r=1\/$ and $\sum_{x \in T} d_{H-S}(x) \geq 1$, then $\gamma (S,T) \geq 0$.
If $r=0\/$ and $\sum_{x\in T} d_{H-S}(x) \geq 1$,
then $V(H)=S \cup T\/$ and
$$\sum_{x\in T} d_{H-S}(x) =\sum_{x\in T} d_{H[T]}(x) = 2 |E(H[T])|
\equiv 0  \pmod{2},$$
and so $\gamma(S,T) \geq 0$.
Therefore it suffices to show that $\sum_{x\in T} d_{H-S}(x) \geq 1$
under the assumption that $q=0\/$ and $0 \leq r \leq 1$.

Suppose that $\sum_{x\in T} d_{H-S}(x)=0$, $q=0\/$ and $0 \leq r \leq 1$.
Let $\overline{S}:= V(G) \setminus S \supseteq T$, $X:=\{x \in
\overline{S} ~|~ d_G(x) \geq n/2\}\/$ and
$Y:= \overline{S}  \setminus X$.
Then
a complete graph $G[Y]\/$ is contained in $C$,
and it follows from $s = (n/2)-2\/$ that for each vertex $x \in X$,
there exist two edges of $C\/$ which join $x\/$ to two vertices in
$\overline{S}$.
Hence we have
\[
|X|+|Y|-1  = | \overline{S} |-1 \geq |E(G[\overline{S}]) \cap E(C)| \geq
|X|+1+|E(G[Y])|
 = |X|+1+\frac{|Y|(|Y|-1)}{2},
\]
which implies $ |Y| \geq 2+ |Y|(|Y|-1)/2$. Now we get a contradiction,
because it is obvious that 
there is no nonnegative integral solution of $|Y|$ to this quadratic
inequality. 
Therefore Claim~1 holds for even $n$.

 We next assume that $n\/$ is odd and $s \geq (n-3)/2$.
Let $q:=s-(n-3)/2 \geq 0\/$ and $r:=n-s-t \geq 0$.
Then it follows from $\rho  \geq 1\/$ and $n \geq 6 \rho -1 \/$ that

\begin{eqnarray*}
 \gamma (S,T) & = & (\rho +1)q+\rho (r+q) + \sum_{x\in T} d_{H-S}(x) +
\frac{n}{2}-3\rho -\frac{3}{2}  \\
	& \geq &  2q + r+q + \sum_{x\in T} d_{H-S}(x) -2.
\end{eqnarray*}
Hence,
by the same argument as above,
 we may assume that $q=0$, $0 \leq r \leq 1\/$ and $\sum_{x\in T}
d_{H-S}(x)=0$.
Let $X:=\{x \in \overline{S} ~|~ d_G(x) \geq (n+1)/2\}\/$ and
$Y:= \overline{S}  \setminus X$.
Then we similarly obtain $|Y| \geq 2+|Y|(|Y|-1)/2$, and derive a contradiction.
Consequently  Claim~1 also holds for odd $n$.

\bigskip
{\bf Claim~2.} ~~
$ T \cap U \not= \emptyset $.

\bigskip
Indeed, assume $T \subseteq W$.
Then $G[T]\/$ is a complete graph and $|E(G[T])|=t(t-1)/2$.
Since $C\/$ is a Hamiltonian cycle,
$|E(G[T]) \cap E(C)| \leq t-1$.
Hence
$$ \sum_{x \in T}d_{H-S}(x) \geq 2|E(G[T]) \setminus E(C)| \geq
t(t-1)-2(t-1)=(t-1)(t-2).$$
Thus
\begin{eqnarray*}
\gamma (S,T) & \geq & (\rho +1)s -\rho t +(t-1)(t-2) \\
	& \geq & (\rho +1)s -\rho t +(t-1)\rho  ~~~~~~~~~~~~~~~~~~~~~~~~~~
 \mbox{(by (\ref{eq:b3}))} \\
	& = & (\rho +1)s - \rho  >0 .~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\mbox{(by (\ref{eq:b2}))}
\end{eqnarray*}
This contradicts (\ref{eq:a2}).

\bigskip
{\bf Claim~3.} ~~
$ T \cap W \not= \emptyset$.

\bigskip
Suppose $T \subseteq U\/$ and $n\/$ is even.
Then for every $x \in T$, we have by (\ref{eq:a3})
$$ \frac{n}{2} \leq d_G(x) \leq d_{H-S}(x)+s+2 \leq \rho  +s+1, $$
which implies $ d_{H-S}(x) \geq (n/2)-s-2\/$ and $\rho +s+2-n/2 \geq 1$.
Hence
\begin{eqnarray*}
\gamma (S,T) & \geq & (\rho +1)s -\rho t +t(\frac{n}{2}-s-2) \\
	& = & (\rho +1)s- t(\rho +s+2 -\frac{n}{2}) \\
	& \geq  & (\rho +1)s- (n-s)(\rho +s+2 -\frac{n}{2}) \\
	& = & ( \rho +1)s
+(\frac{n}{2}-s-3+\frac{n}{2}+3)(\frac{n}{2}-s-3-2\rho + \rho +1) \\
&=& (\frac{n}{2}-s-3)^2 +(\frac{n}{2}-s-3)(\frac{n}{2}+3-2\rho )
+ n -6 \rho  \\
	&  \geq & 0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\mbox{(by $n \geq 8\rho\/$ ~and~ Claim~1)}
\end{eqnarray*}
This contradicts (\ref{eq:a2}).

Next assume $T \subseteq U\/$ and $n\/$ is odd.
Then for every $x \in T$, we have
$$ \frac{n+1}{2} \leq d_G(x) \leq d_{H-S}(x)+s+2 \leq \rho  +s+1, $$
which implies $ d_{H-S}(x) \geq (n/2)-s-(3/2)\/$ and $\rho
+s+(3/2)-(n/2) \geq 1$.
Hence
\begin{eqnarray*}
\gamma (S,T) & \geq & (\rho +1)s -\rho t +t(\frac{n}{2}-s-\frac{3}{2}) \\
	& = & (\rho +1)s- t(\rho +s+\frac{3}{2} -\frac{n}{2}) \\
	& \geq  & (\rho +1)s- (n-s)(\rho +s+\frac{3}{2} -\frac{n}{2}) \\
	&=& ( \frac{n}{2}-s-\frac{5}{2})^2 +(
\frac{n}{2}-s-\frac{5}{2})(\frac{n}{2}+\frac{5}{2}-2\rho ) +n -5\rho  \\
	& \geq & 0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\mbox{(by $n \geq 6\rho -1\/$ and ~Claim~1)}
\end{eqnarray*}
This contradicts (\ref{eq:a2}).
Therefore Claim~2 is proved.

\bigskip
Now put
$$ T_1:=T \cap U, ~~ T_2:=T \cap W, ~~ t_1=|T_1|, ~~ t_2:=|T_2|. $$
By Claims 2 and 3,
we have $t_1 \geq 1$ and $t_2 \geq 1$.
It is clear that $ d_{H-S}(x) \geq d_G(x) -s -2$
for all $x \in T$,
in particular,
for every $y \in T_1$,
\begin{equation}
 d_{H-S}(y) \geq \left\{ \begin{array}{ll}
	\frac{n}{2}-s-2 & ~~\mbox{if ~~ $n$ ~~ is even} \\
	\frac{n}{2}-s- \frac{3}{2} & ~~\mbox{if ~~ $n$ ~~ is odd.}
	\end{array} \right.
\label{eq:a4}
\end{equation}
It follows from (\ref{eq:a3}) that
\begin{equation}
\frac{n}{2} -\rho -s-2  \leq -1 ~~~ \mbox{if $n\/$ is even, ~~and} ~~~
\frac{n}{2}-\rho -s- \frac{3}{2}  \leq -1 ~~~ \mbox{if $n\/$ is odd.}
\label{eq:a4-2}
\end{equation}
By Claim~1 and by the above inequalities,
we have
\begin{equation}
\rho  \geq 2 .
\label{eq:a5}
\end{equation}
For every $x \in T_2$,
we have $d_{H-S}(x) \geq t_2-3\/$ by the fact that $G[W]\/$ is a
complete graph, and obtain the following
inequality from (\ref{eq:a3}).
\begin{equation}
t_2 \leq \rho +2.
\label{eq:a6}
\end{equation}

In order to complete the proof, we consider two cases.
Assume first $n\/$ is even.
By making use of $ n \geq 8\rho$, (\ref{eq:a4}), (\ref{eq:a4-2}),
(\ref{eq:a5}), (\ref{eq:a6}) and Claim~1,
we have
\begin{eqnarray*}
\gamma (S,T) & \geq & (\rho +1)s - \rho (t_1+t_2) + t_1( \frac{n}{2} -s -2) \\
	& = & (\rho +1)s - \rho t_2 + t_1 (\frac{n}{2}-s-2-\rho )  \\
	& \geq &(\rho +1)s -\rho t_2+ (n-s-t_2)( \frac{n}{2} -\rho  -s -2)  \\
	& = &(\frac{n}{2} - s-3) ^2 + (\frac{n}{2} - s-3)(\frac{n}{2}+3-2\rho -t_2)
\\
& & ~~~~~~~ + n-6\rho  -t_2 \\
	& \geq &  2\rho -t_2 \geq  \rho +2 -t_2 \geq 0.
\end{eqnarray*}
This contradicts (\ref{eq:a2}).

We next assume $n\/$ is odd.
Let $r:=n-s-t$.
It is easy to see that
\begin{equation}
 \sum_{x \in T_2}d_{H-S}(x) \geq 2|E(G[T_2]) \setminus E(C)| \geq
t_2(t_2-1) -2(t_2-1)=(t_2-1)(t_2-2) .
\label{eq:a7}
\end{equation}
By using  $n \geq  6\rho -1$, (\ref{eq:a4}), (\ref{eq:a4-2}),
(\ref{eq:a5}) (\ref{eq:a6}) and (\ref{eq:a7}),
we have

\begin{eqnarray*}
\gamma (S,T) & \geq & (\rho +1)s - \rho (t_1+t_2) + t_1( \frac{n}{2} -s
- \frac{3}{2}) +(t_2-1)(t_2-2) \\
	& = & (\rho +1)s+ t_1( \frac{n}{2}-\rho -s- \frac{3}{2})  - \rho t_2
+(t_2-1)(t_2-2)\\
	& \geq &  (\rho +1)s+ (n-s-t_2-r)( \frac{n}{2} -\rho  -s -\frac{3}{2})
-\rho t_2+(t_2-1)(t_2-2) \\
	& = &(\frac{n}{2} - s-\frac{5}{2}) ^2 + (\frac{n}{2} -
s-\frac{5}{2})(\frac{n}{2}+\frac{5}{2}-t_2-2\rho ) \\
 & & ~~~ +n-5\rho +(t_2-1)(t_2-2) -t_2 +r(\rho +s+ \frac{3}{2}-\frac{n}{2}) \\
 & = & (\frac{n}{2} - s-\frac{5}{2})^2+ \rho -1 + (t_2-1)(t_2-2) -t_2 +r .
\end{eqnarray*}
Since $(t_2-1)(t_2-2) -t_2 \geq -2\/$ with equality only when $t_2=2\/$,
we have $\rho -1 +(t_2-1)(t_2-2) -t_2 +r \geq \rho -1-2 +r=\rho -2+r-1
\geq r-1$ and thus 
$\gamma (S,T) \geq 0\/$ unless $s=(n-5)/2$, $t_2=2\/$ $r=0$, $\rho =2\/$
and (\ref{eq:a7}) holds with equality.
Since $t_2=2\/$ and (\ref{eq:a7}) holds with equality,
 $$ |E(G[T_2])|=|E(G[T_2]) \cap E(C)|=1. $$
Since $s=(n+1)/2-3\/$ and $\rho =2$,
it follows from (\ref{eq:a3}) and (\ref{eq:a4}) that
$$ d_{H-S}(x)=1 ~~\mbox{and} ~~~ d_G(x)=\frac{n+1}{2} ~~~~
 \mbox{for all} ~~~ x \in T_1. $$

\noindent This implies that all the edges of $C\/$ incident with
vertices in $T_1\/$ are contained
in $E(G[T]) \setminus E(G[T_2])$,
and thus the number of such edges is at least $t_1+1$.
Therefore $|E(G[T]) \cap C| \geq t_1+1+1 =t$,
contradicting the fact that $C\/$ is a Hamiltonian cycle of $G$.
Consequently the theorem is proved.

\vskip 0.2 cm

\bigskip

\noindent {\bf Remark.} 
The condition that $n \ge 8k-16\/$ for even $n\/$ and $n \ge 6k-13\/$
for odd $n$
in Theorem~\ref{th:clk} are best possible.
To see this, either let $n\/$ be an even integer such that  $2k \le n <
8k-16\/$ and
 put $m = (n/2)+2$, or
let $n\/$ be an odd integer such that $2k-1 \le n < 6k-13$
and  put $m =(n+3)/2$.
Let $C_m=(v_1v_2 \ldots v_m)\/$ be a cycle of order $m\/$ and
$P_{n-m}=(v_{m+1}v_{m+2} \ldots v_n)\/$ a path of order $n-m$.
Then the join $G:=C_m + P_{n-m}\/$ has no $[k,\, k+1]$-factor
containing Hamiltonian cycle $(v_1v_2 \ldots v_n)\/$
but satisfies $\delta (G) \geq k$ and $d_G(x) + d_G(y) \ge n$ for all
nonadjacent vertices $x\/$ and $y\/$ of $G$.

We  explain why $G$ has no such factor when $n$ is even.
By  setting $S=\{v_{m+1}, \ldots ,v_n\}$ and $T=\{v_1, \ldots ,v_m\}$
in (\ref{eq:a2}),
we obtain $\gamma (S,T)=(k-1)(n/2-2)-(k-2)(n/2+2)+2 <0\/$,
which implies $G$ has no such factor.



\vskip 0.5 cm

\begin{thebibliography}{99}
\bibitem{bm} J.A. Bondy and U.S.R. Murty,~~
{\sl Graph Theory with
Applications}, American Elsevier, New York (1976).
\bibitem{cai} Cai Mao-cheng, ~~
Connected [$k$, $k+1$]-factors of graphs,
submitted.
\bibitem{in} T. Iida and T. Nishimura,~~
 An Ore-type condition for the existence
of $k$-factors in graphs,
 {\sl Graphs and Combinat.} {\bf 7} (1991) 353-361.
\bibitem{kan} M. Kano,~~
 Some current results and problems on factors of
graphs, {\sl Proc. 3rd China-USA Internat. Conf. on Graph Theory and Its
Application}, World Sci. Publishing, River Edge,
NJ, (1994) 93-98.
\bibitem{ca} Yanjun Li and Cai Mao-cheng,~~ A degree condition for the
existence
of connected factors, {\sl Australasian Journal of Combinatorics} {\bf
14} (1995) 77-83.
\bibitem{lic} Yanjun Li and Cai Mao-cheng,~~ A degree condition for
graphs to have 
$[a,b]$-factors, {\sl J. Graph Theory} {\bf 27} (1998) 1-6.
\bibitem{lo} L. Lov\'{a}sz,~~
 Subgraphs with prescribed valencies, {\sl J.
Combin. Theory} {\bf 8} (1970) 391-416.
\bibitem{ni} T. Nishimura,~~
 A degree condition for the existence of $k$-factors,
{\sl J. Graph Theory} {\bf 16} (1992) 141-151.
\bibitem{ore} O. Ore,~~A note on Hamilton circuit,
{\sl Amer. Math. Soc.} {\bf 4} (1947) 107-111.
\bibitem{tutte} W.T. Tutte,~~ Graph factors, {\sl Combinatorica} {\bf 1} (1981)
79-97.
\bibitem{wz} B. Wei and Y. Zhu,~~
 Hamiltonian $k$-factors in graphs, submitted.
\end{thebibliography}

\end{document}