\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{}{}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{case}{Case}
\newtheorem{subcase}{Case}[case]
\newtheorem{subsubcase}{Case}[subcase]
\newtheorem{subsubsubcase}{Case}[subsubcase]

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcounter{mathitem}
\newenvironment{mathitem}
  {\begin{list}{{$(\arabic{mathitem})$}}{
   \setcounter{mathitem}{0}
   \usecounter{mathitem}
   \setlength{\topsep}{0pt plus 2pt minus 0pt}
   \setlength{\parskip}{0pt plus 2pt minus 0pt}
   \setlength{\partopsep}{0pt plus 2pt minus 0pt}
   \setlength{\parsep}{0pt plus 2pt minus 0pt}
   \setlength{\leftmargin}{35pt}
   \setlength{\itemindent}{-15pt}
   %\setlength{\listparindent}{-20pt}
   \setlength{\itemsep}{0pt plus 2pt minus 0pt}}}
  {\end{list}}

\newcommand{\pa}{{\rm par}}

\allowdisplaybreaks[4]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf The Ramsey numbers of paths versus wheels: a complete
solution}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Binlong Li$^{1,2}$ \qquad Bo Ning$^1$\\
\small $^1$Department of Applied Mathematics\\[-0.8ex]
\small Northwestern Polytechnical University\\[-0.8ex]
\small Xi'an, Shaanxi 710072, P.R.~China\\
\small $^2$European Centre of Excellence NTIS\\[-0.8ex]
\small 306 14 Plze\v n, Czech Republic\\
\small \tt libinlong@mail.nwpu.edu.cn,
ningbo\_math84@mail.nwpu.edu.cn }

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Dec 14, 2013}{Sep 19, 2014}{}\\
\small Mathematics Subject Classifications: 05C55, 05D10}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
Let $G_1$ and $G_2$ be two given graphs. The Ramsey number
$R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$
on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$
contains a $G_2$. We denote by $P_n$ the path on $n$ vertices and
$W_m$ the wheel on $m+1$ vertices. Chen et al. and Zhang determined
the values of $R(P_n,W_m)$ when $m\leq n+1$ and when $n+2\leq m\leq
2n$, respectively. In this paper we determine all the values of
$R(P_n,W_m)$ for the left case $m\geq 2n+1$. Together with Chen et
al.'s and Zhang's results, we give a complete solution to the
problem of determining the Ramsey numbers of paths versus wheels.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Ramsey number; Path; Wheel
\end{abstract}

\section{Introduction}

We use Bondy and Murty \cite{Bondy_Murty} for terminology and
notation not defined here, and consider finite simple graphs only.

Let $G$ be a graph. We denote by $\nu(G)$ the order of $G$, by
$\delta(G)$ the minimum degree of $G$, and by $\omega(G)$ the
component number of $G$. We denote by $P_n$ and $C_n$ the path and
cycle on $n$ vertices, respectively. The \emph{wheel} on $n+1$
vertices, denoted by $W_n$, is the graph obtained by joining a
vertex to each vertex of a $C_n$.

Let $G_1$ and $G_2$ be two graphs. The \emph{Ramsey number}
$R(G_1,G_2)$, is defined as the least integer $r$ such that for
every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or
$\overline{G}$ contains a $G_2$, where $\overline{G}$ is the
complement of $G$. If $G_1$ and $G_2$ are both complete, then
$R(G_1,G_2)$ is the classical Ramsey number $r(\nu(G_1),\nu(G_2))$.
Otherwise, $R(G_1,G_2)$ is usually called the \emph{generalized
Ramsey number}.

In 1967, Gerencs\'er and Gy\'arf\'as \cite{Gerencser_Gyarfas}
computed the Ramsey numbers of all path-path pairs, and gave the
first generalized Ramsey number formula. (In fact, this question of
determining Ramsey numbers of paths versus paths appeared in a paper
of Erd\H{o}s \cite{Erdos} in 1947, and the right upper bound was
also determined there.) After that, Faudree et al.
\cite{Faudree_Lawrence_Parsons_Schelp} determined the Ramsey numbers
of paths versus cycles. We list these results as bellow, both of
them will be used in this paper.

\begin{theorem}[Gerencs\'er and Gy\'arf\'as
\cite{Gerencser_Gyarfas}]\label{Th1} If $m\geq n\geq 2$, then
\begin{align*}
R(P_n,P_m)=m+\left\lfloor\frac{n}{2}\right\rfloor-1.
\end{align*}
\end{theorem}

\begin{theorem}[Faudree et al.
\cite{Faudree_Lawrence_Parsons_Schelp}]\label{Th2} If $n\geq 2$ and
$m\geq 3$, then
\begin{align*}
R(P_n,C_m)=\left\{\begin{array}{ll}
2n-1,           & \mbox{for } n\geq m \mbox{ and } m \mbox{ is odd};\\
n+m/2-1,        & \mbox{for } n\geq m \mbox{ and } m \mbox{ is even};\\
\max\{m+\lfloor n/2\rfloor-1,2n-1\},    & \mbox{for } m>n \mbox{ and
}
                    m \mbox{ is odd};\\
m+\lfloor n/2\rfloor-1,     & \mbox{for } m>n \mbox{ and } m \mbox{
                    is even}.
\end{array}\right.
\end{align*}
\end{theorem}

Recently, graph theorists have begun to investigate the Ramsey
numbers of paths versus wheels. Baskoro and Surahmat
\cite{Bakoro_Surahmat} conjectured the values of $R(P_n,W_m)$ when
$n\geq m-1$, and got some partial results. Chen et al.
\cite{Chen_Zhang_Zhang} completely determined the values of
$R(P_n,W_m)$ when $n\geq m-1$. Salman and Broersma
\cite{Salman_Broersma} further generalized Chen et al.'s result.
Zhang \cite{Zhang} firstly obtained all the values of $R(P_n,W_m)$
when $n+2\leq m\leq 2n$. We list the results of Chen et al.'s and
Zhang's in the following.

\begin{theorem}[Chen et al. \cite{Chen_Zhang_Zhang}]\label{Th3}
If $3\leq m\leq n+1$, then
\begin{align*}
R(P_n,W_m)=\left\{\begin{array}{ll}
3n-2,   &m \mbox{ is odd};\\
2n-1,   &m \mbox{ is even}.
\end{array}\right.
\end{align*}
\end{theorem}

\begin{theorem}[Zhang \cite{Zhang}]\label{Th4}
If $n+2\leq m\leq 2n$, then
\begin{align*}
R(P_n,W_m)=\left\{\begin{array}{ll}
3n-2,   &m \mbox{ is odd};\\
m+n-2,  &m \mbox{ is even}.
\end{array}\right.
\end{align*}
\end{theorem}

For the case $m\geq 2n+1$, some upper bounds and lower bounds of
$R(P_n,W_m)$ were given \cite{Salman_Broersma,Zhang}. Furthermore,
for some $n,m$, the exact values of $R(P_n,W_m)$ were also
determined in \cite{Salman_Broersma,Zhang}.

In this paper we will prove the following formula, which can be used
to determine all the values of $R(P_n,W_m)$ for the left case $m\geq
2n+1$.

\begin{theorem}\label{Th5}
If $n\geq 2$ and $m\geq 2n+1$, then
\begin{align*}
R(P_n,W_m)=\left\{\begin{array}{ll}
(n-1)\cdot\beta+1,  &\alpha\leq\gamma;\\
\lfloor(m-1)/\beta\rfloor+m,  &\alpha>\gamma,
\end{array}\right.
\end{align*}
where
\begin{align*}
\alpha=\frac{m-1}{n-1},\ \beta=\lceil\alpha\rceil \mbox{ and }
\gamma=\frac{\beta^2}{\beta+1}.
\end{align*}
\end{theorem}

Together with Theorems \ref{Th3} and \ref{Th4}, we give a complete
solution to the problem of determining the Ramsey numbers of paths
versus wheels.

%
\section{Preliminaries}
%

Before our proof we will first list one result due to Zhang
\cite{Zhang} and give some additional terminology and notation.
Second, we will prove a series of lemmas which support our proof of
the main theorem.

The following result is a rewriting of two corollaries in
\cite{Zhang}. It helps us to deal with the cases $n=3,4$ in our
proof.

\begin{theorem}[Zhang \cite{Zhang}]\label{Th6}
If $n\geq 3$ and $m\geq 2n+1$, then
$$R(P_n,W_m)=\left\{\begin{array}{ll}
m+n-1,  & \mbox{if } m\equiv 1\mod(n-1);\\
m+n-2,  & \mbox{if } m\equiv 0,2\mod(n-1).
\end{array}\right.$$
\end{theorem}

For integers $s,t$, the \emph{interval} $[s,t]$ is the set of
integers $i$ with $s\leq i\leq t$. Note that if $s>t$, then
$[s,t]=\emptyset$. Let $X$ be a subset of $\mathbb{N}$. We set
$\mathcal {L}(X)=\{\sum_{i=1}^kx_i: x_i\in X, k\in \mathbb{N}\}$,
and suppose $0\in\mathcal{L}(X)$ for any set $X$. Note that if $1\in
X$, then $\mathcal{L}(X)=\mathbb{N}$. For an interval $[s,t]$, we
use $\mathcal{L}[s,t]$ instead of $\mathcal{L}([s,t])$.

In the following of the paper, $n$ always denotes an integer at
least 2 and $m$ an integer at least 3. We denote by $\pa(n)$ the
parity of $n$, i.e., $\pa(n)=\lceil n/2\rceil-\lfloor n/2\rfloor$.

For integers $n,m$, let $t(n,m)$ be the values of $R(P_n,W_m)$
defined in Theorem 5, that is,
$$t(n,m)=\left\{\begin{array}{ll}
(n-1)\cdot\beta+1,  &\alpha\leq\gamma;\\
\lfloor(m-1)/\beta\rfloor+m,  &\alpha>\gamma,
\end{array}\right.$$
where
$$\alpha=\frac{m-1}{n-1}, \beta=\lceil\alpha\rceil \mbox{ and }
\gamma=\frac{\beta^2}{\beta+1}.$$

\begin{lemma}\label{Le1}
  If $m\geq 2n+1$, then $t(n,m)=\min\{t: t\notin \mathcal {L}[t-m+1,n-1]\}$.
\end{lemma}

\begin{proof}
Set $T=\{t: t\in\mathcal{L}[t-m+1,n-1]\}$. Note that if $t\in T$,
then $t-1\in T$. So it is sufficient to prove that
$t(n,m)=\max(T)+1$.

Note that
\begin{align*}
t\in T  & \Leftrightarrow t\in\mathcal{L}[t-m+1,n-1]\\
        & \Leftrightarrow t\in[k(t-m+1),k(n-1)], \mbox{ for some integer } k\\
        & \Leftrightarrow t\leq\frac{k}{k-1}(m-1) \mbox{ and } t\leq k(n-1),
            \mbox{ for some integer } k\\
        & \Leftrightarrow t\leq k(n-1) \mbox{ for some integer } k<\alpha+1,
            \mbox{ or}\\
        & \ \ \ \ \ t\leq\left\lfloor\frac{m-1}{k-1}\right\rfloor+m-1,
                    \mbox{ for some integer } k\geq\alpha+1.
\end{align*}
This implies that
\begin{align*}
T=\left\{t: t\leq k(n-1), k\leq\beta\right\}\cup\left\{t:
t\leq\left\lfloor\frac{m-1}{k-1}\right\rfloor+m-1,
k\geq\beta+1\right\}.
\end{align*}
Thus
\begin{align*}
\max(T) & =\max\left\{(n-1)\beta,
            \left\lfloor\frac{m-1}{\beta}\right\rfloor+m-1\right\}\\
        & =\left\{\begin{array}{ll}
            (n-1)\cdot\beta,                &\alpha\leq\gamma;\\
            \lfloor(m-1)/\beta\rfloor+m-1,  &\alpha>\gamma.
            \end{array}\right.
\end{align*}
We conclude that $t(n,m)=\max(T)+1$.
\end{proof}

\begin{lemma}\label{Le2}
Let $p$ be an integer, and $G$ be a graph on at least three
vertices.
\begin{mathitem}
\item If $G$ is 2-connected and
$\delta(G)\geq\lceil p/2\rceil$, then $G$ contains a cycle of order
at least $\min\{\nu(G),p\}$.
\item If $x\in V(G)$, $G$ is connected and $d(v)\geq p-1$ for
every vertex $v\in V(G)\backslash\{x\}$, then $G$ contains a path
from $x$ of order at least $p$.
\item If $x,y\in V(G)$, $G+xy$ is 2-connected and $d(v)\geq p-1$ for
every vertex $v\in V(G)\backslash\{x,y\}$, then $G$ contains a path
from $x$ to $y$ of order at least $p$.
\item If $x,y\in V(G)$, $G+xy$ is 2-connected
and $d(v)\geq\lceil p/2\rceil$ for every vertex $v\in
V(G)\backslash\{x,y\}$, then $G$ contains a path from $x$ of order
at least $\min\{\nu(G),p\}$.
\item If $G$ is connected and $\delta(G)\geq\lfloor p/2\rfloor$,
then $G$ contains a path of order at least $\min\{\nu(G),p\}$.
\item If $x\in V(G)$, $G$ is connected, and $d_{G-x}(v)\geq
p-2$ for every vertex $v\in V(G)\backslash\{x\}$, then $G$ contains
a path from $x$ of order at least $p$.
\item If $x\in V(G)$, $G$ is 2-connected and
$d_{G-x}(v)\geq\lfloor p/2\rfloor$ for every vertex $v\in
V(G)\backslash\{x\}$, then $G$ contains a path from $x$ of order at
least $\min\{\nu(G),p\}$.
\end{mathitem}
\end{lemma}

\begin{proof}
The assertions (1), (2) and (3) are results of Dirac \cite{Dirac},
Erd\H{o}s and Gallai \cite{Erdos_Gallai}, respectively. Now we prove
the other assertions.

(4) Let $G'=G+xy$. Since every two nonadjacent vertices of $G'$
contain one with degree at least $\lceil p/2\rceil$, by Fan's
theorem \cite{Fan}, $G'$ contains a cycle $C$ with order at least
$\min\{\nu(G),p\}$. If $C$ does not contain the added edge $xy$,
then $C$ is a cycle of $G$ and $G$ contains a path from $x$ of order
at least $\min\{\nu(G),p\}$; if $C$ contains the added edge $xy$,
then $P=C-xy$ is a path of $G$ from $x$ of order at least
$\min\{\nu(G),p\}$.

(5) We add a new vertex $x$ and join $x$ to every vertex of $G$. We
denote the resulting graph as $G'$. Thus every vertex in $V(G')$ has
degree at least $\lfloor p/2\rfloor+1=\lceil(p+1)/2\rceil$. By (1),
$G'$ contains a cycle $C$ of order at least $\min\{\nu(G'),p+1\}$,
and $P=C-x$ is a path of $G$ of order at least $\min\{\nu(G),p\}$.

(6) Let $H$ be a component of $G-x$, and let $x'$ be a neighbor of
$x$ in $H$. Note that every vertex in $H$ has degree at least $p-2$
in $H$. By (2), $H$ contains a path $P$ from $x'$ of order at least
$p-1$. Thus $P'=xx'P$ is a path of $G$ from $x$ of order at least
$p$.

(7) Let $G'=G-x$. If $G'$ contains a vertex with degree 1, then
$p\leq 3$ and the assertion is trivially true. Now we assume that
$\delta(G')\geq 2$.

We first assume that $G'$ is 2-connected. By (1), $G'$ contains a
cycle $C$ of order at least $\min\{\nu(G'),p-\pa(p)\}$. Let $P$ be a
path from $x$ to $C$, let $x'$ be the end-vertex of $P$ on $C$, and
let $x''$ be a neighbor of $x'$ on $C$. Then $P'=P\cup C-x'x''$
(with the obvious meaning) is a path from $x$ of order at least
$\min\{\nu(G),p\}$.

Now we assume that $G'$ is separable. Then every end-block of $G'$
is 2-connected. Let $B$ be an end-block of $G'$, and $b$ be the
cut-vertex of $G'$ contained in $B$. Since $G$ is 2-connected, $x$
is adjacent to some vertex, say $x'$, in $B-b$. By (3), $B$ contains
a path $P$ from $x'$ to $b$ of order at least $\lfloor
p/2\rfloor+1$, and by (2), $G'-(B-b)$ contains a path $P'$ from $b$
of order at least $\lfloor p/2\rfloor+1$. Thus $P''=xx'PbP'$ is a
path from $x$ of order at least $p$.
\end{proof}

\begin{lemma}\label{Le3}
If $G$ is a disconnected graph such that
\begin{mathitem}
\item $m\leq \nu(G)$; and
\item every component of $G$ has order at most $\lfloor
m/2\rfloor$,
\end{mathitem}
then $\overline{G}$ contains a $C_m$.
\end{lemma}

\begin{proof}
Let $G'$ be an induced subgraph of $G$ of order $m$. Clearly every
component of $G'$ has order at most $\lfloor m/2\rfloor$. Thus every
vertex of $G'$ has degree at least $\lceil m/2\rceil$ in
$\overline{G'}$. By Lemma \ref{Le2}, $\overline{G'}$ contains a
$C_m$.
\end{proof}

\begin{lemma}\label{Le4}
Let $G$ be a graph.
\begin{mathitem}
\item If $n\leq\nu(G)\leq\lfloor3n/2\rfloor-2$ and $G$ contains no
$P_n$, then $\overline{G}$ contains a path of order $2\nu(G)+3-2n$.
\item If $\nu(G)\geq\lfloor3n/2\rfloor-1$ and $G$ contains no $P_n$,
then $\overline{G}$ contains a path of order $\nu(G)+1-\lfloor
n/2\rfloor$.
\item If $n\geq 4$ is even, $\nu(G)\geq3n/2-1$, and $G$ contains no
$C_n$ then $\overline{G}$ contains a path of order $\nu(G)+1-n/2$.
\end{mathitem}
\end{lemma}

\begin{proof}
The lemma can be deduced by Theorems \ref{Th1} and \ref{Th2}.
\end{proof}

\begin{lemma}\label{Le5}
Let $G_1$ and $G_2$ be two disjoint graphs. If
\begin{mathitem}
\item $\overline{G_1}$ contains a path of order $p\geq 2$; and
\item $m\leq\min\{2\nu(G_1),\nu(G_1)+\nu(G_2),p+2\nu(G_2)-1\}$,
\end{mathitem}
then $\overline{G_1\cup G_2}$ contains a $C_m$.
\end{lemma}

\begin{proof}
We first assume that $\nu(G_2)\geq\lfloor m/2\rfloor$. If $m$ is
even, then $\nu(G_1)\geq m/2$ and $\nu(G_2)\geq m/2$. Let
$x_1,x_2,\ldots,x_k$ be $k=m/2$ vertices in $G_1$, and let
$y_1,y_2,\ldots,y_k$ be $k$ vertices in $G_2$. Then
$C=x_1y_1x_2y_2\cdots x_ky_kx_1$ is a $C_m$ in $\overline{G_1\cup
G_2}$. If $m$ is odd, then then $\nu(G_1)\geq(m+1)/2$ and
$\nu(G_2)\geq(m-1)/2$. Note that $G_1$ has two nonadjacent vertices.
Let $x_1,x_2,\ldots,x_k$ be $k=(m+1)/2$ vertices in $G_1$ such that
$x_1x_k\notin E(G_1)$, and let $y_1,y_2,\ldots,y_{k-1}$ be $k-1$
vertices in $G_2$. Then $C=x_1y_1x_2y_2\cdots x_{k-1}y_{k-1}x_kx_1$
is a $C_m$ in $\overline{G_1\cup G_2}$.

Now we assume that $\nu(G_2)\leq\lfloor m/2\rfloor-1$. Let
$V(G_2)=\{y_1,y_2,\cdots,y_k\}$, where $k=\nu(G_2)$. Since $2\leq
m+1-2k\leq p$, $\overline{G_1}$ contains a path $P$ of order
$m+1-2k$. Let $s,t$ be the two end-vertices of $P$. Note that
$\nu(G_1)-\nu(P)\geq m-k-m-1+2k=k-1$. Let $x_1,x_2,\ldots,x_{k-1}$
be $k-1$ vertices in $V(G_1-P)$. Then $C=sy_1x_1y_2x_2\cdots
x_{k-1}y_ktP$ is a $C_m$ in $\overline{G_1\cup G_2}$.
\end{proof}

\begin{lemma}\label{Le6}
Suppose $m\geq 2n+1$. Let $G$ be a disconnected graph containing no
$P_n$. If
\begin{mathitem}
\item $m\leq \nu(G)$; and
\item the order sum of every $\omega(G)-1$ components in $G$ is at least
$m+\lfloor n/2\rfloor-\nu(G)$,
\end{mathitem}
then $\overline{G}$ contains a $C_m$.
\end{lemma}

\begin{proof}
If every component of $G$ has order at most $\lfloor m/2\rfloor$,
then we are done by Lemma \ref{Le3}. Now we assume that there is a
component $H$ with order at least $\lfloor m/2\rfloor+1$.

Let $G_1=H$, and $G_2=G-H$. Note that $m\leq 2\nu(G_1)$,
$m\leq\nu(G)=\nu(G_1)+\nu(G_2)$ and $\nu(G_2)\geq m+\lfloor
n/2\rfloor-\nu(G)$.

Note that $\nu(G_1)\geq\lfloor m/2\rfloor+1\geq n$. If
$\nu(G_1)\leq\lfloor3n/2\rfloor-2$, then by Lemma \ref{Le4},
$\overline{G_1}$ contains a path of order $p=2\nu(G_1)+3-2n$. Since
\begin{align*}
p+2\nu(G_2)-1   & =2\nu(G_1)+3-2n+2\nu(G_2)-1\\
                & =2\nu(G)+2-2n\\
                & \geq 2m+2-2n\\
                & \geq m,
\end{align*}
by Lemma \ref{Le5}, $\overline{G}$ contains a $C_m$. If
$\nu(G_1)\geq\lfloor3n/2\rfloor-1$, then by Lemma \ref{Le4},
$\overline{G_1}$ contains a path of order $p=\nu(G_1)+1-\lfloor
n/2\rfloor$. Since
\begin{align*}
p+2\nu(G_2)-1   & =\nu(G_1)+1-\left\lfloor\frac{n}{2}\right\rfloor+2\nu(G_2)-1\\
                & =\nu(G)+\nu(G_2)-\left\lfloor\frac{n}{2}\right\rfloor\\
                & \geq\nu(G)+m+\left\lfloor\frac{n}{2}\right\rfloor-\nu(G)
                    -\left\lfloor\frac{n}{2}\right\rfloor\\
                & =m,
\end{align*}
by Lemma \ref{Le5}, $\overline{G}$ contains a $C_m$.
\end{proof}

\begin{lemma}\label{Le7}
Let $G$ be a graph, $X$ an independent set of $G$, $R=G-X$. If
\begin{mathitem}
\item $|X|\geq 3$;
\item every component of $R$ is joined to at most one vertex in $X$;
\item $\overline{R}$ contains a path of order $p\geq 2$; and
\item $m\leq\min\{\nu(G),p+2|X|-3\}$,
\end{mathitem}
then $\overline{G}$ contains a $C_m$.
\end{lemma}

\begin{proof}
Let $P$ be a path in $\overline{R}$ with the largest order. Clearly
$\nu(P)\geq p$.

If $\nu(P)\geq m-1$, then let $P'$ be a subpath of $P$ of order
$m-1$. Let $s,t$ be the two end-vertices of $P'$. Since each of $s$
and $t$ is adjacent to at most one vertex in $X$ and $|X|\geq 3$,
there is a vertex $x$ in $X$ nonadjacent to both $s$ and $t$. Thus
$C=sxtP'$ is a $C_m$ in $\overline{G}$. Now we assume that
$\nu(P)\leq m-2$.

Let $s,t$ be the two end-vertices of $P$. If $P$ contains all
vertices in $R$, then $\nu(P)=\nu(R)$. Let $x$ be a vertex in $X$
nonadjacent to $s$, and $x'$ be a vertex in $X\backslash\{x\}$
nonadjacent to $t$. Note that $|X|=\nu(G)-\nu(R)\geq m-\nu(P)$. Let
$x_1,x_2,\ldots,x_k$ be $k=m-\nu(P)$ vertices in $X$ such that
$x_1=x$ and $x_k=x'$, then $C=sx_1x_2\cdots x_ktP$ is a $C_m$ in
$\overline{G}$. Now we assume that $V(R)\backslash
V(P)\neq\emptyset$.

Let $U=V(R-P)$. Note that each of $s,t$ is adjacent to every vertex
in $U$, and this implies that $U\cup\{s,t\}$ is contained in a
component of $R$. Thus $U\cup\{s,t\}$ is joined to at most one
vertex in $X$. Let $y$ be the vertex in $X$ that is joined to
$U\cup\{s,t\}$. If such a vertex does not exist, then let $y$ be any
one vertex in $X$.

Note that $m-\nu(P)\leq m-p\leq 2|X|-3$. If $m-\nu(P)$ is odd, then
$|X|\geq(m-\nu(P)+1)/2+1$. Let $x_1,x_2,\ldots,x_k$ be
$k=(m-\nu(P)+1)/2$ vertices in $X\backslash\{y\}$, and let
$u_1,\ldots,u_{k-1}$ be $k-1$ vertices in $U\cup
X\backslash\{x_1,x_2,\ldots,x_k\}$. Then $C=sx_1u_1x_2u_2\cdots
x_{k-1}u_{k-1}x_ktP$ is a $C_m$ in $\overline{G}$. If $m-\nu(P)$ is
even, then $m-\nu(P)\leq 2|X|-4$ and $|X|\geq(m-\nu(P))/2+2$. Let
$x_1,x_2,\ldots,x_k$ be $k=(m-\nu(P))/2+1$ vertices in
$X\backslash\{y\}$, and let $u_1,\ldots,u_{k-2}$ be $k-2$ vertices
in $U\cup X\backslash\{x_1,x_2,\ldots,x_k\}$. Then
$C=sx_1u_1x_2u_2\cdots x_{k-2}u_{k-2}$ $x_{k-1}x_ktP$ is a $C_m$ in
$\overline{G}$.
\end{proof}

\begin{lemma}\label{Le8}
Let $G$ be a graph, $X_1,X_2$ two independent sets of $G$ (possibly
joint), $X=X_1\cup X_2$, $R=G-X$. If
\begin{mathitem}
\item $|X_1|=|X_2|\geq 3$, $|X_1\backslash
X_2|=|X_2\backslash X_1|\geq 2$;
\item every component of $R$ is joined to at most one vertex in $X_i$, $i=1,2$;
\item $\overline{R}$ contains a path of order $p\geq 2$; and
\item $m\leq\min\{\nu(G),p+2|X|-5\}$,
\end{mathitem}
then $\overline{G}$ contains a $C_m$.
\end{lemma}

\begin{proof}
We first define an \emph{adjustable segment} of a cycle $C$. If
$X_1\cap X_2=\emptyset$, then let $x_1,x'_1,x''_1\in X_1$,
$x_2,x'_2,x''_2\in X_2$ and $u\in V(R)$, and we call a subpath $A$
an adjustable segment of $C$ with the center $u$ if one of the
following is true:
\begin{mathitem}
\item $A=x_1x'_1ux'_2x_2$ with $x''_1,x''_2\notin V(C)$;
\item $A=x_1x'_1x''_1ux'_2x_2$ with $x''_2\notin V(C)$;
\item $A=x_1x'_1ux''_2x'_2x_2$ with $x''_1\notin V(C)$; or
\item $A=x_1x'_1x''_1ux''_2x'_2x_2$.
\end{mathitem}
If $X_1\cap X_2\neq\emptyset$, then let $x_1,x'_1\in X_1\backslash
X_2$, $x_2,x'_2\in X_2\backslash X_1$ and $x\in X_1\cap X_2$, and we
call a subpath $A$ an adjustable segment of $C$ with the center $x$
if one of the following is true:
\begin{mathitem}
\item $A=x_1xx_2$ with $x'_1,x'_2\notin V(C)$;
\item $A=x_1x'_1xx_2$ with $x'_2\notin V(C)$;
\item $A=x_1xx'_2x_2$ with $x'_1\notin V(C)$; or
\item $A=x_1x'_1xx'_2x_2$.
\end{mathitem}

If $X_1\cap X_2\neq\emptyset$, then let $P$ be a path in
$\overline{R}$ with the largest order; if $X_1\cap X_2=\emptyset$,
then let $P$ be a non-Hamilton path in $\overline{R}$ with the
largest order.

If $\nu(P)\geq m-5$, then let $P'$ be a subpath of $P$ of order
$m-5$ and $s,t$ be the two end-vertices of $P'$. If $X_1\cap
X_2\neq\emptyset$, then let $x$ be a vertex in $X_1\cap X_2$, $x_1$
a vertex in $X_1\backslash X_2$ nonadjacent to $s$, $x'_1$ a vertex
in $X_1\backslash(X_2\cup\{x_1\})$, $x_2$ a vertex in $X_2\backslash
X_1$ nonadjacent to $t$ and $x'_2$ a vertex in
$X_2\backslash(X_1\cup\{x_2\})$. Then $C=sx_1x'_1xx'_2x_2tP'$ is a
$C_m$ in $\overline{G}$. If $X_1\cap X_2=\emptyset$, then let $u$ be
a vertex in $V(R-P')$, $x_1$ a vertex in $X_1$ nonadjacent to $s$,
$x'_1$ a vertex in $X_1\backslash\{x_1\}$ nonadjacent to $u$, $x_2$
a vertex in $X_2$ nonadjacent to $t$ and $x'_2$ a vertex in
$X_2\backslash\{x_2\}$ nonadjacent to $u$. Then
$C=sx_1x'_1ux'_2x_2tP'$ is a $C_m$ in $\overline{G}$.

Now we assume that $\nu(P)\leq m-6$. By a similar argument in the
analysis above, we can get a cycle $C$ in $\overline{G}$ of order at
least $\nu(P)+5$ such that
\begin{mathitem}
\item[(a)] $C$ contains $P$ as a subpath;
\item[(b)] $C$ contains an adjustable segment $A$ (with end-vertices $x_1,x_2$);
\item[(c)] every edge of $C$ has a vertex in $R$, unless it is an edge in
$A$.
\end{mathitem}

Now we choose a cycle $C$ in $\overline{G}$ satisfying (a)(b)(c)
with order as large as possible but at most $m$. If $\nu(C)=m$, then
we are done. So we assume that $\nu(C)\leq m-1$. We claim that
$V(R)\subset V(C)$. Assume the contrary. Let $v$ be a vertex in
$U=V(R)\backslash V(C)$.

If ($X_1\cap X_2=\emptyset$ and) $A=x_1x'_1ux'_2x_2$ with $x''_1\in
X_1\backslash V(C)$, $x''_2\in X_2\backslash V(C)$, then
$C'=C-x_1x'_1\cup x_1x''_1x'_1$ is a required cycle with order
$\nu(C)+1$, a contradiction. Using the same analysis, we can
conclude that $A=x_1x'_1x''_1ux''_2x'_2x_2$ (if $X_1\cap
X_2=\emptyset$) or $A=x_1x'_1xx'_2x_2$ (if $X_1\cap
X_2\neq\emptyset$).

If $X_1\cap X_2\neq\emptyset$, then $P$ is a longest path of
$\overline{R}$; if $X_1\cap X_2=\emptyset$, then noting that $u,v\in
V(R-P)$, $P$ is a longest path of $\overline{R}$ as well. Thus
$\nu(P)\geq p$ and $U\cup\{s,t\}$ is contained in a component of
$R$. If there is a vertex $y$ in $X$ that is joined to
$U\cup\{s,t\}$, then we use $y$ instead of the vertex $x'_1$, $x'_2$
or $x$ in $C$, for the case $y\in X_1\backslash X_2$, $y\in
X_2\backslash X_1$, or $y\in X_1\cap X_2$, respectively. Thus we
assume that every vertex in $X\backslash\{x'_1,x'_2,x\}$ is not
joined to $U\cup\{s,t\}$.

If every vertex in $X$ is in $V(C)$, then noting that there are at
most 5 vertices in $X$ each of which has a successor on $C$ such
that it is not in $U$, we have
\begin{align*}
\nu(C)\geq\nu(P)+|X|+(|X|-5)\geq p+2|X|-5\geq m,
\end{align*}
a contradiction. So we assume that there is a vertex $x'$ in $X$
which is not in $C$. Let $v'$ be the predecessor of $x_1$ in $C$.
Clearly $v'\in U\cup\{s,t\}$. Then
$C'=v'x'vx_1x''_1\overrightarrow{C}[x''_1,v']$ (if $X_1\cap
X_2=\emptyset$) or $C'=v'x'vx_1x\overrightarrow{C}[x,v']$ (if
$X_1\cap X_2\neq\emptyset$) is a required cycle of order $\nu(C)+1$,
a contradiction. Thus as we claimed, every vertex in $R$ is in $C$.
This implies that $C$ is a cycle in $\overline{G}$ satisfying
\begin{mathitem}
\item[(d)] there is an edge $x_1x'_1\in E(C)$ such that $x_1,x'_1\in X_1$;
\item[(e)] there is an edge $x_2x'_2\in E(C)$ such that $x_2,x'_2\in X_2$;
\item[(f)] $V(R)\subset V(C)$.
\end{mathitem}

Now we choose a cycle $C$ in $\overline{G}$ satisfying (d)(e)(f)
with order as large as possible but at most $m$. If $\nu(C)=m$, then
we are done. So we assume that $\nu(C)\leq m-1$. If every vertex in
$X$ is in $C$, then
\begin{align*}
\nu(C)=\nu(R)+|X|\geq m,
\end{align*}
a contradiction. So we assume that there is a vertex $x'$ in $X$
which is not in $C$. If $x'\in X_1$, then $C'=C-x_1x'_1\cup
x_1x'x'_1$ is a required cycle of order $\nu(C)+1$; if $x'\in X_2$,
then $C'=C-x_2x'_2\cup x_2x'x'_2$ is a required cycle of order
$\nu(C)+1$, a contradiction.

Thus the lemma holds.
\end{proof}

The proof of the next lemma is similar as the proof of Lemma
\ref{Le8}, but more involved.

\begin{lemma}\label{Le9}
Let $G$ be a graph, $R$ be an induced subgraph of $G$, $X_1,X_2$ two
independent sets of $G-R$ (possibly joint), $X=X_1\cup X_2$. If
\begin{mathitem}
\item $|X_1|=|X_2|\geq 3$, $|X_1\backslash
X_2|=|X_2\backslash X_1|\geq 2$;
\item every component of $R$ has order at least 2;
\item every component of $R$ is joined to at most one vertex in $X_i$, $i=1,2$;
\item for any component $H$ of $R$, there are at least $q$ vertices
in $G-R$ each of which is either in $X$ or not joined to $H$;
\item $\overline{R}$ contains a path of order $p\geq 2$; and
\item $m\leq\min\{\lceil3\nu(R)/2\rceil+4,\nu(R)+q-1,p+2q-5\}$,
\end{mathitem}
then $\overline{G}$ contains a $C_m$.
\end{lemma}

\begin{proof}
We use the concept of an adjustable segment defined in Lemma
\ref{Le8}. If $X_1\cap X_2\neq\emptyset$, then let $P$ be a path in
$\overline{R}$ with the largest order; if $X_1\cap X_2=\emptyset$,
then let $P$ be a non-Hamilton path in $\overline{R}$ with the
largest order.

If $\nu(P)\geq m-5$, then similar as in Lemma \ref{Le8}, we can find
a $C_m$ in $\overline{G}$. Thus we assume that $\nu(P)\leq m-6$. By
a similar argument as in Lemma \ref{Le8}, we can get a cycle $C$ in
$\overline{G}$ of order at least $\nu(P)+5$ such that
\begin{mathitem}
\item[(a)] $C$ contains $P$ as a subpath;
\item[(b)] $C$ contains an adjustable segment $A$ (with end-vertices
$x_1,x_2$);
\item[(c)] every edge of $C$ has a vertex in $R$, unless it is an edge in
$A$.
\end{mathitem}

Now we choose a cycle $C$ in $\overline{G}$ satisfying (a)(b)(c)
with order as large as possible but at most $m$. If $\nu(C)=m$, then
we are done. So we assume that $\nu(C)\leq m-1$. We claim that
$V(R)\subset V(C)$. Assume the contrary. Let $v$ be a vertex in
$U=V(R-C)$.

Using the same analysis in Lemma 8, we can conclude that
$A=x_1x'_1x''_1ux''_2x'_2x_2$ (if $X_1\cap X_2=\emptyset$) or
$A=x_1x'_1xx'_2x_2$ (if $X_1\cap X_2\neq\emptyset$) and $P$ is a
longest path of $\overline{R}$. Thus $\nu(P)\geq p$ and
$U\cup\{s,t\}$ is contained in a common component of $R$.
Furthermore, we can assume that every vertex in
$X\backslash\{x'_1,x'_2,x\}$ is not joined to $U\cup\{s,t\}$.

Let $W$ be the union of $X$ and the set of vertices in $G-R$ that
are not joined to $U\cup\{s,t\}$. Then $|W|\geq q$. If every vertex
in $W$ is in $V(C)$, then noting that there are at most 5 vertices
in $W$ each of which has a successor on $C$ such that it is not in
$U$, we have
\begin{align*}
\nu(C)\geq\nu(P)+|W|+(|W|-5)\geq p+2q-5\geq m,
\end{align*}
a contradiction. So we assume that there is a vertex $w$ in $W$ that
is not in $V(C)$. Let $v'$ be the predecessor of $x_1$ in $C$.
Clearly $v'\in U\cup\{s,t\}$. Then
$C'=v'wvx_1x''_1\overrightarrow{C}[x''_1,v']$ (if $X_1\cap
X_2=\emptyset$) or $C'=v'wvx_1x\overrightarrow{C}[x,v']$ (if
$X_1\cap X_2\neq\emptyset$) is a required cycle of order $\nu(C)+1$,
a contradiction. Thus as we claimed, every vertex in $R$ is in $C$.
This implies $C$ satisfies (b)(c) and
\begin{mathitem}
\item[(d)] $V(R)\subset V(C)$.
\end{mathitem}
Now we choose a cycle $C$ in $\overline{G}$ satisfying (b)(c)(d)
with order as large as possible but at most $m$. If $\nu(C)=m$, then
we are done. So we assume that $\nu(C)\leq m-1$. By a similar
argument as above, we can conclude that
$A=x_1x'_1x''_1ux''_2x'_2x_2$ (if $X_1\cap X_2=\emptyset$) or
$A=x_1x'_1xx'_2x_2$ (if $X_1\cap X_2\neq\emptyset$).

We claim that there are two vertices $u_1,u_2$ in $C$ such that
$u_1,u_2$ are in a common component of $R$ and $u_1^+,u_2^+\in
V(R)$. Assume the contrary. Note that every component of $R$ has at
least 2 vertices, there is at most one vertex in a component, such
that it has a successor on $C$ in $R$, and there are 4 vertices of
$C$ (in the adjusted segment) each of which is not a successor of
some vertex in $R$. Thus
\begin{align*}
\nu(C)\geq\nu(R)+\left\lceil\frac{\nu(R)}{2}\right\rceil+4=
    \left\lceil\frac{3\nu(R)}{2}\right\rceil+4\geq m,
\end{align*}
a contradiction. Thus as we claimed, there are two edges
$u_1u_1^+,u_2u_2^+$ such that $u_1,u_2$ are in a common component of
$R$ and $u_1^+,u_2^+\in V(R)$.

If there is a vertex $y$ in $X\backslash V(C)$ that is joined to
$\{u_1,u_2\}$, then we use $y$ instead of the vertex $x'_1$, $x'_2$
or $x$ in $C$. Thus we assume that every vertex in $X\backslash
V(C)$ is not joined to $\{u_1,u_2\}$. Let $W$ be the union of $X$
and the set of vertices in $G-R$ that are not joined to
$\{u_1,u_2\}$. Then $|W|\geq q$. If every vertex in $W$ is in $C$,
then
\begin{align*}
\nu(C)\geq\nu(R)+|W|\geq \nu(R)+q\geq m,
\end{align*}
a contradiction. Thus we assume that there is a vertex $w$ in $W$
that is not in $C$.

If $u_1^+,u_2^+$ are in distinct components of $R$, then
$C'=u_1wu_2\overleftarrow{C}[u_2,u_1^+]u_1^+u_2^+\overrightarrow{C}[u_2^+,u_1]$
is a required cycle with order $\nu(C)+1$. Now we assume that
$u_1^+,u_2^+$ are in a common component of $R$.

If there is a vertex $y'$ in $X\backslash\{w\}$ that is joined to
$\{u_1^+,u_2^+\}$, then we use $y'$ instead of the vertex $x'_1$,
$x'_2$ or $x$ in $C$. Thus we assume that every vertex in
$X\backslash V(C)\backslash\{w\}$ is not joined to
$\{u_1^+,u_2^+\}$.

Let $W'$ be the union of $X$ and the set of vertices in $G-R$ that
are not joined to $\{u_1^+,u_2^+\}$. Then $|W'|\geq q$. If every
vertex in $W'\backslash\{w\}$ is in $C$, then
\begin{align*}
\nu(C)\geq\nu(R)+|W'|-1\geq\nu(R)+q-1\geq m,
\end{align*}
a contradiction. Thus we assume that there is a vertex $w'$ in
$W\backslash\{w\}$ that is not in $C$. Let
$C'=u_1wu_2\overleftarrow{C}[u_2,u_1^+]u_1^+w'u_2^+\overrightarrow{C}[u_2^+,u_1]$.
Then $C''=C'-x_1x'_1x''_1\cup x_1x''_1$ (if $X_1\cap X_2=\emptyset$)
or $C''=C'-x_1x'_1x\cup x_1x$ (if $X_1\cap X_2\neq\emptyset$) is a
required cycle of order $\nu(C)+1$, a contradiction.
\end{proof}

%
\section{Proof of Theorem \ref{Th5}}
%

The case of $n=2$ is trivial. For the case of $n=3$ or $n=4$, we are
done by Theorem \ref{Th6}. Thus in the following we will assume that
$n\geq 5$.

By Lemma \ref{Le1}, $t(n,m)=\min\{t: t\notin \mathcal
{L}[t-m+1,n-1]\}$. Let $t=t(n,m)$. Thus $t-1\in \mathcal
{L}[t-m,n-1]$. Let $t-1=\sum_{i=1}^k t_i$, where $t_i\in[t-m,n-1]$,
$1\leq i\leq k$. Let $G$ be a graph with $k$ components
$H_1,\ldots,H_k$ such that $H_i$ is a clique on $t_i$ vertices. Note
that $G$ contains no $P_n$ since every component of $G$ has less
than $n$ vertices; and $\overline{G}$ contains no $W_m$ since every
vertex of $G$ has less than $m$ nonadjacent vertices. Thus $G$ is a
graph on $t-1$ vertices such that $G$ contains no $P_n$ and
$\overline{G}$ contains no $W_m$. This implies that $R(P_n,W_m)\geq
t$.

Now we will prove that $R(P_n,W_m)\leq t$. Assume not. Let $G$ be a
graph on $t$ vertices such that $G$ contains no $P_n$ and
$\overline{G}$ contains no $W_m$.

Let $s=m+n-t$ (i.e., $\nu(G)=m+n-s$).

\begin{claim}\label{Cl1}
  $1\leq s\leq \lfloor(n+5)/4\rfloor$.
\end{claim}

\begin{proof}
Let $t'=m+n-1$. Since $t'-m+1=n$, $[t'-m+1,n-1]=\emptyset$, and
$t'\notin \mathcal {L}(\emptyset)=\{0\}$, we have $t\leq t'=m+n-1$.
This implies that $s\geq 1$ (and $t-m+1\leq n$).

Now we prove that $s\leq (n+5)/4$. By Lemma \ref{Le1}, $t\notin
\mathcal {L}[t-m+1,n-1]$. Thus $t\notin[k(t-m+1),k(n-1)]$, for every
$k$. That is, $t\in[k(n-1)+1,(k+1)(t-m+1)-1]$, for some $k$, which
implies
\begin{align*}
t\geq k(n-1)+1 \mbox{ and } t\geq\frac{k+1}{k}m-1,
\end{align*}
for some $k$.

If $k\leq 2$, then we have $t\leq 3(t-m+1)-1$, and
\begin{align*}
t\geq\frac{k+1}{k}m-1\geq\frac{3}{2}m-1>3n-1\geq 3(t-m+1)-1,
\end{align*}
a contradiction. Thus we assume that $k\geq 3$.

If $m\leq(k^2n-k^2+2k)/(k+1)$, then
\begin{align*}
  s &=m+n-t\leq \frac{k^2n-k^2+2k}{k+1}+n-(k(n-1)+1)\\
    &=\frac{n+2k-1}{k+1}\leq\frac{n+5}{4}.
\end{align*}

If $m>(k^2n-k^2+2k)/(k+1)$, then
\begin{align*}
  s &=m+n-t\leq m+n-(\frac{k+1}{k}m-1)\\
    &=n-\frac{m}{k}+1<n-\frac{k^2n-k^2+2k}{k(k+1)}+1\\
    &=\frac{n+2k-1}{k+1}\leq\frac{n+5}{4}.
\end{align*}

Thus the claim holds.
\end{proof}

We list the possible values of $s$ for $n\leq 16$.

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
  \hline \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} 
  $n$ & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\
  \hline
  $s\leq$ & 2 & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 & 5 & 5\\
  \hline \hline
\end{tabular}\\[3mm]
{Table 1: The possible values of $s$ for $n\leq 16$.}
\end{center}

\begin{claim}\label{Cl2}
Let $v$ be an arbitrary vertex of $G$ and $G'$ be an induced
subgraph of $G-v-N(v)$. Then $\overline{G'}$ contains no $C_m$.
\end{claim}

\begin{proof}
  Otherwise, noting that $v$ is nonadjacent to every vertex in the
  $C_m$, there will be a $W_m$ in $\overline{G}$ (with the hub $v$).
\end{proof}

\begin{claim}\label{Cl3}
  $\delta(G)\geq \lceil n/2\rceil-s+1$.
\end{claim}

\begin{proof}
Assume the contrary. Let $v$ be a vertex of $G$ with $d(v)\leq
\lceil n/2\rceil-s$. Then $G'=G-v-N(v)$ has at least $m+\lfloor n/2
\rfloor-1$ vertices. Since $G'$ contains no $P_n$, by Theorem
\ref{Th2}, $\overline{G'}$ contains a $C_m$ (note that $m\geq
2n+1$), a contradiction to Claim \ref{Cl2}.
\end{proof}

From Claims \ref{Cl1} and \ref{Cl3}, one can see that $\delta(G)\geq
2$ (when $n\geq 5$).

\begin{case}
  $G$ is disconnected.
\end{case}

\begin{subcase}
  Every component of $G$ has order less than $n$.
\end{subcase}

Let $H_i$, $1\leq i\leq k=\omega(G)$, be the components of $G$.
Since $t\notin \mathcal {L}[t-m+1,n-1]$, there is a component, say
$H_1$, with order at most $t-m$. Thus $\sum_{i=2}^k\nu(H_i)\geq m$.
Since $\nu(H_i)\leq n-1\leq\lfloor m/2\rfloor$. By Lemma \ref{Le3},
$\overline{G-H_1}$ contains a $C_m$, a contradiction.

\begin{subcase}
  There is a component of $G$ with order at least $n$.
\end{subcase}

Let $H$ be a component of $G$ with the largest order. Note that
$\nu(H)\geq n$. If every vertex of $H$ has degree at least $\lfloor
n/2\rfloor$, then by Lemma \ref{Le2}, $H$ contains a $P_n$, a
contradiction. Thus there is a vertex $v$ in $H$ with
$d(v)\leq\lfloor n/2\rfloor-1$. Let $G'=G-v-N(v)$. Then
\begin{align*}
\nu(G') & =\nu(G)-1-d(v)\\
        & \geq m+n-s-1-\left\lfloor\frac{n}{2}\right\rfloor+1\\
        & =m+\left\lceil\frac{n}{2}\right\rceil-s\geq m.
\end{align*}

Since $\nu(H)\geq n>1+d(v)$, $G'$ is disconnected. Let $\mathcal{H}$
be the union of $\omega(G')-1$ components of $G'$. We will prove
that $\nu(\mathcal{H})\geq m+\lfloor n/2\rfloor-\nu(G')$.

Let $H'$ be a component of $G$ other than $H$. If
$H'\not\subset\mathcal{H}$, then
$\nu(\mathcal{H})=\nu(G')-\nu(H')\geq\nu(G')-\lfloor\nu(G)/2\rfloor$,
and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\nu(G')-\left\lfloor\frac{\nu(G)}{2}\right\rfloor+\nu(G')
        -m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq 2\left(m+\left\lceil\frac{n}{2}\right\rceil-s\right)-
        \left\lfloor\frac{m+n-s}{2}\right\rfloor-m
        -\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil 2\left(m+\frac{n}{2}-s\right)-
        \frac{m+n-s}{2}-m-\frac{n}{2}\right\rceil\\
    & =\left\lceil\frac{m-3s}{2}\right\rceil
        \geq\left\lceil\frac{2n+1-3s}{2}\right\rceil\geq 0.
\end{align*}
If $H'\subset\mathcal{H}$, then
$\nu(\mathcal{H})\geq\nu(H')\geq\delta(G)+1$, and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\delta(G)+1+\nu(G')-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil\frac{n}{2}\right\rceil-s+2+
       m+\left\lceil\frac{n}{2}\right\rceil
       -s-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & =\left\lceil\frac{n}{2}\right\rceil+\pa(n)+2-2s\geq 0.
\end{align*}

Now by Lemma \ref{Le6}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{case}
  $G$ has connectivity 1.
\end{case}

Note that $\delta(G)\geq 2$. Every end-block of $G$ is 2-connected.

\begin{subcase}
  Every end-block of $G$ has order at most $\lceil m/2\rceil$.
\end{subcase}

\begin{claim}\label{Cl4}
Let $G'$ be a disconnected subgraph of $G$. If
\begin{mathitem}
\item $\nu(G')\geq m$; and
\item there are two components of $G'$, each of which is an end-block
removing a cut-vertex of $G$ contained in the end-block,
\end{mathitem}
then the order sum of every $\omega(G')-1$ components in $G'$ is at
least $m+\lfloor n/2\rfloor-\nu(G')$.
\end{claim}

\begin{proof}
Let $B-x$ and $B'-x'$ be two components of $G'$, where $B,B'$ are
two end-blocks of $G$ and $x,x'$ are two cut-vertices of $G$
contained in $B$ and $B'$, respectively.

Let $\mathcal {H}$ be the union of any $\omega(G')-1$ components of
$G'$. We first assume that $\mathcal{H}$ does not contain $B-x$ or
$B'-x'$. Without loss of generality, we assume that $\mathcal{H}$
does not contain $B-x$. Then
$\nu(\mathcal{H})=\nu(G')-\nu(B-x)\geq\nu(G')-\lceil m/2\rceil+1$,
and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\nu(G')-\left\lceil\frac{m}{2}\right\rceil+1+\nu(G')-
        m-\left\lceil\frac{n}{2}\right\rceil\\
    & \geq2m-\left\lceil\frac{m}{2}\right\rceil+1-
        m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & =\left\lfloor\frac{m}{2}\right\rfloor-
        \left\lfloor\frac{n}{2}\right\rfloor+1\geq 0.
\end{align*}
Now we assume that both $B-x$ and $B'-x'\subset\mathcal {H}$. Then
$\nu(\mathcal{H})\geq\nu(B-x)+\nu(B'-x')\geq 2\delta(G)$, and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq 2\delta(G)+\nu(G')-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq2\left(\left\lceil\frac{n}{2}\right\rceil-s+1\right)+
        m-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & =\left\lceil\frac{n}{2}\right\rceil+\pa(n)+2-2s\geq 0.
\end{align*}

Thus the claim holds.
\end{proof}

\begin{subsubcase}
  $G$ has only two end-blocks.
\end{subsubcase}

Let $B$ and $B'$ be the two end-blocks of $G$, and let $x$ and $x'$
be the cut-vertices of $G$ contained in $B$ and $B'$, respectively.
Note that
\begin{align*}
\nu(G)-\nu(B)-\nu(B')\geq
m+n-s-2\cdot\left\lceil\frac{m}{2}\right\rceil=n-s-\pa(m)\geq 1.
\end{align*}
This implies that $V(G)\backslash(V(B)\cup V(B'))\neq\emptyset$.

Note that in this case $G-(B-x)-(B'-x')+xx'$ is 2-connected. If
every vertex in $G-B-B'$ has degree at least $2s-\pa(n)-3$, then by
Lemma \ref{Le2}, there is a path from $x$ to $x'$ of order at least
$2s-\pa(n)-2$. Note that $B$ contains a path from $x$ of order at
least $\lceil n/2\rceil-s+2$, and $B'$ contains a path from $x'$ of
order at least $\lceil n/2\rceil-s+2$. Thus $G$ contains a $P_n$, a
contradiction. This implies that there is a vertex $v$ in $G-B-B'$
with $d(v)\leq 2s-\pa(n)-4$.

Let $G'=G-x-x'-v-N(v)$. Then
\begin{align*}
\nu(G') & \geq\nu(G)-3-d(v)\\
        & \geq m+n-s-3-2s+\pa(n)+4\\
        & =m+n+\pa(n)+1-3s\geq m.
\end{align*}

By Claim \ref{Cl4}, the order sum of every $\omega(G')-1$ components
in $G'$ is at least $m+\lfloor n/2\rfloor-\nu(G')$. By Lemma
\ref{Le6}, $\overline{G'}$ contains a $C_m$, a contradiction.

\begin{subsubcase}
  $G$ has at least three end-blocks.
\end{subsubcase}

Let $x$ and $x'$ be two cut-vertices of $G$ such that the longest
path between $x$ and $x'$ in $G$ is as long as possible. Clearly $x$
and $x'$ are both contained in some end-blocks. Let $B$ and $B'$ be
two end-blocks of $G$ containing $x$ and $x'$, respectively ($B\neq
B'$). Let $v$ be a vertex in $V(B-x)\cup V(B'-x')$ such that
$d_{G-x-x'}(v)$ is as small as possible. We assume without loss of
generality that $v\in V(B-x)$.

\begin{claim}\label{Cl5}
\begin{align*}
d_{B-x}(v)\leq\left\{\begin{array}{ll}
\lfloor n/2\rfloor-2,   & \mbox{if } x=x';\\
\lceil n/2\rceil-3,     & \mbox{if } xx' \mbox{ is a cut-edge of } G;\\
\lfloor n/2\rfloor-3,   & \mbox{otherwise}.
\end{array}\right.
\end{align*}
\end{claim}

\begin{proof}
We set a parameter $a$ such that $a=0$ if $x=x'$, 1 if $xx'$ is a
cut-edge of $G$, and 2 otherwise. So there is a path between $x$ and
$x'$ of length at least $a$.

If $\delta(B-x)\geq\lfloor(n-a)/2\rfloor-1$, then
$\delta(B'-x')\geq\lfloor(n-a)/2\rfloor-1$. By Lemma \ref{Le2}, $B$
contains a path from $x$ of order at least $\lfloor(n-a)/2\rfloor+1$
and $B'$ contains a path from $x'$ of order at least
$\lfloor(n-a)/2\rfloor+1$. Thus $G$ contains a path of order at
least $n+1-\pa(n-a)\geq n$, a contradiction. Now we obtain that
$\delta(B-x)\leq\lfloor(n-a)/2\rfloor-2$.
\end{proof}

\begin{subsubsubcase}
  $x=x'$.
\end{subsubsubcase}

In this case, $G$ has only one cut-vertex $x$. Let $G'=G-x-v-N(v)$.
Then
\begin{align*}
\nu(G') & =\nu(G)-2-d_{B-x}(v)\\
        & \geq m+n-s-2-\left\lfloor\frac{n}{2}\right\rfloor+2\\
        & =m+\left\lceil\frac{n}{2}\right\rceil-s\geq m.
\end{align*}

Note that every end-block of $G$ other than $B$ removing $x$ is a
component of $G'$. By Claim \ref{Cl4} and Lemma \ref{Le6},
$\overline{G'}$ contains a $C_m$, a contradiction.

\begin{subsubsubcase}
  $xx'$ is a cut-edge of $G$.
\end{subsubsubcase}

In this case, $G$ has only two cut-vertices $x$ and $x'$. Let
$G'=G-x-x'-v-N(v)$. Then
\begin{align*}
\nu(G') & =\nu(G)-3-d_{B-x}(v)\\
        & \geq m+n-s-3-\left\lceil\frac{n}{2}\right\rceil+3\\
        & =m+\left\lfloor\frac{n}{2}\right\rfloor-s\geq m.
\end{align*}

Note that every end-block of $G$ other than $B$ removing $x$ or $x'$
is a component of $G'$. By Claim \ref{Cl4} and Lemma \ref{Le6},
$\overline{G'}$ contains a $C_m$, a contradiction.

\begin{subsubsubcase}
  $xx'\notin E(G)$ or $xx'$ is not a cut-edge of $G$.
\end{subsubsubcase}

Let $B''$ be an end-block of $G$ other than $B$ and $B'$, and let
$x''$ be the cut-vertex of $G$ contained in $B''$ (possibly $x''=x$
or $x'$). Let $G'=G-x-x'-x''-v-N(v)$. Then
\begin{align*}
\nu(G') & \geq\nu(G)-4-d_{B-x}(v)\\
        & \geq m+n-s-4-\left\lfloor\frac{n}{2}\right\rfloor+3\\
        & =m+\left\lceil\frac{n}{2}\right\rceil-s-1\geq m.
\end{align*}

Note that $B'-x'$ and $B''-x''$ are two components of $G'$. By Claim
\ref{Cl4} and Lemma \ref{Le6}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{subcase}
  There is an end-block of $G$ with order at least $\lceil m/2\rceil+1$.
\end{subcase}

Let $B$ be an end-block of $G$ with the maximum order, and $x$ be
the cut-vertex of $G$ contained in $B$. Let $x'$ be a cut-vertex of
$G$ such that the longest path between $x$ and $x'$ is as long as
possible. Clearly $x'$ is contained in some end-blocks. Let $B'$ be
an end-block of $G$ containing $x'$ ($B\neq B'$). Let $v$ be a
vertex in $B-x$ such that $d_{B-x}(v)$ is as small as possible.

\begin{claim}\label{Cl6}
\begin{align*}
d_{B-x}(v)\leq\left\{\begin{array}{ll}
\lceil(n+2s-\pa(n))/4\rceil-2,      & \mbox{if } x=x';\\
\lfloor(n+2s-\pa(n))/4\rfloor-2,    & \mbox{if } xx' \mbox{ is a cut-edge of } G;\\
\lceil(n+2s-\pa(n))/4\rceil-3,      & \mbox{otherwise}.
\end{array}\right.
\end{align*}
\end{claim}

\begin{proof}
We set a parameter $a$ such that $a=0$ if $x=x'$, 1 if $xx'$ is a
cut-edge of $G$, and 2 otherwise. So there is a path between $x$ and
$x'$ of length at least $a$.

By Claim \ref{Cl3} and Lemma \ref{Le2}, $B'$ contains a path from
$x'$ of order at least $\lceil n/2\rceil-s+2$, and $G-(B-x)$
contains a path from $x$ of order at least $\lceil n/2\rceil-s+a+2$.

Note that $\nu(B)\geq\lceil m/2\rceil+1\geq\lfloor
n/2\rfloor+s-a-1$. If $\delta(B-x)\geq\lfloor(\lfloor
n/2\rfloor+s-a-1)/2\rfloor$, then by Lemma \ref{Le2}, $B$ contains a
path from $x$ of order at least $\lfloor n/2\rfloor+s-a-1$. Thus $G$
contains a $P_n$, a contradiction. This implies that
\begin{align*}
\delta(B-x)\leq\left\lfloor\frac{\lfloor
n/2\rfloor+s-a-1}{2}\right\rfloor-1
=\left\lceil\frac{n+2s-\pa(n)-2a}{4}\right\rceil-2.
\end{align*}
Thus the claim holds.
\end{proof}

Note that
\begin{align*}
\nu(B-x-v-N(v))
    & =\nu(B)-2-d_{B-x}(v)\\
    & \geq\left\lceil\frac{m}{2}\right\rceil+1-2
        -\left\lceil\frac{n+2s-\pa(n)}{4}\right\rceil+2\\
    & \geq\left\lceil\frac{m}{2}-\frac{n+2s+2}{4}\right\rceil+1\\
    & \geq\left\lceil\frac{3n-2s}{4}\right\rceil+1\geq 1.
\end{align*}
This implies that $V(B)\backslash(\{x,v\}\cup N(v))\neq\emptyset$.

\begin{subsubcase}
  $x=x'$.
\end{subsubcase}

In this case, $G$ has only one cut-vertex $x$. Let $G'=G-x-v-N(v)$.
Then $G'$ is disconnected and
\begin{align*}
\nu(G') & =\nu(G)-2-d_{B-x}(v)\\
        & \geq m+n-s-2-\left\lceil\frac{n+2s-\pa(n)}{4}\right\rceil+2\\
        & =m+\left\lfloor\frac{3n+\pa(n)-6s}{4}\right\rfloor\geq m.
\end{align*}

Let $\mathcal {H}$ be the union of any $\omega(G')-1$ components of
$G'$. We will prove that $\nu(\mathcal{H})\geq m+\lfloor
n/2\rfloor-\nu(G')$.

If $B'-x\not\subset\mathcal{H}$, then
$\nu(\mathcal{H})=\nu(G')-\nu(B'-x)\geq\nu(G')-
\lfloor(\nu(G)-1)/2\rfloor$, and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\nu(G')-\left\lfloor\frac{\nu(G)-1}{2}\right\rfloor+\nu(G')
        -m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq 2\left(m+\left\lfloor\frac{3n+\pa(n)-6s}{4}\right\rfloor\right)
        -\left\lfloor\frac{m+n-s-1}{2}\right\rfloor-m
        -\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil m+2\cdot\frac{3n-6s-2}{4}
        -\frac{m+n-s-1}{2}-\frac{n}{2}\right\rceil\\
    & =\left\lceil\frac{m+n-5s-1}{2}\right\rceil\geq
        \left\lceil\frac{3n-5s}{2}\right\rceil\geq 0.
\end{align*}

Now we assume that $B'-x\subset\mathcal{H}$. In this case
$\nu(\mathcal{H})\geq\nu(B'-x)\geq\delta(G)$, and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\delta(G)+\nu(G')-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil\frac{n}{2}\right\rceil-s+1+m
        +\left\lfloor\frac{3n+\pa(n)-6s}{4}\right\rfloor
        -m-\left\lfloor \frac{n}{2}\right\rfloor\\
    & \geq\left\lfloor\frac{3n+5\pa(n)+4-10s}{4}\right\rfloor.
\end{align*}
Note that $3n+5\pa(n)+4-10s\geq 0$ unless $n=8$ and $s=3$.

\noindent\textbf{Petty Case.} $n=8$ and $s=3$.

In this case $\nu(B'-x)\geq 2$ and $d_{B-x}(v)\leq 2$. If
$\nu(\mathcal{H})\geq 3$, or if $d_{B-x}(v)=1$, then it is easy to
see that $\nu(\mathcal{H})\geq m+\lfloor n/2\rfloor-\nu(G')$. Now we
assume that $\nu(B'-x)=\nu(\mathcal{H})=2$ and $d_{B-x}(v)=2$. This
implies that $B'$ is a triangle, there are only two blocks $B,B'$,
and every vertex in $B-x$ has degree at least 2 in $B-x$. If $B-x$
has a cut-vertex, then noting that every end-block of $B-x$ has at
least three vertices, $B$ contains a path from $x$ of order at least
6, and $G$ contains a $P_8$, a contradiction. So we assume that
$B-x$ is 2-connected.

Note that $B-x$ contains a cycle of order at least 4. Let $C$ be a
longest cycle of $B-x$. If $\nu(C)\geq 5$, then there is also an
path from $x$ in $B$ of order at least 6, a contradiction. Thus we
assume that $\nu(C)=4$. If there is a component of $B-x-C$ with
order at least 2, or if there is a vertex in $B-x-C$ adjacent to two
consecutive vertices on $C$, then it is easy to find a cycle longer
than $C$. Thus $B-x-C$ consists of isolated vertices and every
vertex is adjacent to two nonconsecutive vertices on $C$. If there
are two vertices in $B-x-C$ adjacent to different vertices on $C$,
we can also find a longer cycle. Thus all the vertices of $B-x-C$
have the same neighbors on $C$. This implies that $B-x-v-N(v)$ is
disconnected and then $\nu(\mathcal{H})\geq\nu(B'-x)+1=3$. Thus we
also have $\nu(\mathcal{H})\geq m+\lfloor n/2\rfloor-\nu(G')$.

By Lemma \ref{Le6}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{subsubcase}
  $xx'$ is a cut-edge of $G$ and there is only one end-block containing $x'$.
\end{subsubcase}

Let $G'=G-x-v-N(v)$. Then $B'$ is a component of $G'$, and
\begin{align*}
\nu(G') &=\nu(G)-2-d_{B-x}(v)\\
        & \geq m+n-s-2-\left\lfloor\frac{n+2s-\pa(n)}{4}\right\rfloor+2\\
        & =m+\left\lceil\frac{3n+\pa(n)-6s}{4}\right\rceil\geq m.
\end{align*}

Now let $\mathcal {H}$ be the union of any $\omega(G')-1$ components
of $G'$. If $B'\not\subset\mathcal{H}$, then
$\nu(\mathcal{H})=\nu(G')-\nu(B')\geq\nu(G')-\lfloor\nu(G)/2\rfloor$,
and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -\left\lfloor\frac{n}{2}\right\rfloor-m
    \geq\nu(G')-\left\lfloor\frac{\nu(G)}{2}\right\rfloor+\nu(G')
        -m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq 2\left(m+\left\lceil\frac{3n+\pa(n)-6s}{4}\right\rceil\right)
        -\left\lfloor\frac{m+n-s}{2}\right\rfloor
        -m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil m+2\cdot\frac{3n-6s}{4}
        -\frac{m+n-s}{2}-\frac{n}{2}\right\rceil\\
    & =\left\lceil\frac{m+n-5s}{2}\right\rceil\geq
        \left\lceil\frac{3n+1-5s}{2}\right\rceil\geq 0.
\end{align*}
If $B'\subset\mathcal {H}$, then
$\nu(\mathcal{H})\geq\nu(B')\geq\delta(G)+1$, and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\delta(G)+1+\nu(G')-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil\frac{n}{2}\right\rceil-s+2+
        m+\left\lceil\frac{3n+\pa(n)-6s}{4}\right\rceil-
        m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & =\left\lceil\frac{3n+5\pa(n)+8-10s}{4}\right\rceil\geq 0.
\end{align*}

By Lemma \ref{Le6}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{subsubcase}
  $xx'\notin E(G)$, or $xx'$ is not a cut-edge of $G$, or there
  are at least two end-blocks of $G$ containing $x'$.
\end{subsubcase}

Let $G'=G-x-x'-v-N(v)$. Note that in this case $\omega(G')\geq 3$,
and we have
\begin{align*}
    \nu(G') &=\nu(G)-3-d_{B-x}(v)\\
    & \geq m+n-s-3-\left\lfloor\frac{n+2s-\pa(n)}{4}\right\rfloor+2\\
    & =m+\left\lceil\frac{3n+\pa(n)-6s-4}{4}\right\rceil\geq m.
\end{align*}

Now let $\mathcal {H}$ be the union of any $\omega(G')-1$ components
of $G'$. If $B'-x'\not\subset\mathcal{H}$, then
$\nu(\mathcal{H})=\nu(G')-\nu(B'-x')\geq\nu(G')-\lfloor\nu(G)/2\rfloor+1$,
and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\nu(G')-\left\lfloor\frac{\nu(G)}{2}\right\rfloor+1+\nu(G')
        -m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq 2\left(m+\left\lceil\frac{3n+\pa(n)-6s-4}{4}\right\rceil\right)
        -\left\lfloor\frac{m+n-s}{2}\right\rfloor+1
        -m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil m+2\cdot\frac{3n-6s-4}{4}-\frac{m+n-s}{2}+1
        -\frac{n}{2}\right\rceil\\
    & =\left\lceil\frac{m+n-5s-2}{2}\right\rceil
        \geq\left\lceil\frac{3n-5s-1}{2}\right\rceil\geq 0.
\end{align*}
If $B'-x'\subset\mathcal {H}$, then noting that $\omega(G')\geq 3$,
$\nu(\mathcal{H})\geq\nu(B'-x')+1\geq\delta(G)+1$, and
\begin{align*}
\nu(\mathcal{H})+\nu(G')& -m-\left\lfloor\frac{n}{2}\right\rfloor
    \geq\delta(G)+1+\nu(G')-m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & \geq\left\lceil\frac{n}{2}\right\rceil-s+2+
        m+\left\lceil\frac{3n+\pa(n)-6s-4}{4}\right\rceil-
        m-\left\lfloor\frac{n}{2}\right\rfloor\\
    & =\left\lceil\frac{3n+5\pa(n)+4-10s}{4}\right\rceil\geq 0.
\end{align*}

By Lemma \ref{Le6}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{case}
  $G$ is 2-connected.
\end{case}

By Claim \ref{Cl3} and Lemma \ref{Le2}, $G$ contains a cycle of
order at least $2(\lceil n/2\rceil-s+1)=n-2s+\pa(n)+2$. Let $C$ be a
longest cycle of $G$ (with a given orientation). Suppose that
$\nu(C)=n-r$, where
$$r\leq 2s-\pa(n)-2.$$

For a vertex $x$ of $C$, we use $x^+$ to denote the successor, and
$x^-$ the predecessor, of $x$ on $C$. For a subset $X$ of $V(C)$, we
set $X^+=\{x^+: x\in X\}$ and $X^-=\{x^-: x\in X\}$.

Let $H$ be a subgraph of a component of $G-C$, and let
$N_C(H)=\{z_1,z_2,\ldots z_k\}$, where $k=d_C(H)$, and $z_i$, $1\leq
i\leq k$, are in order along $C$. We call the subpath
$\overrightarrow{C}[z_i,z_{i+1}]$ (the indices are taken modulo $k$)
a \emph{good segment} of $C$ (with respect to $H$); moreover, if
$z_i$ and $z_{i+1}$ are joined to two distinct vertices $x,y$ in
$H$, then we call $\overrightarrow{C}[z_i,z_{i+1}]$ a \emph{better
segment} of $C$ (with respect to $H$); moreover, if there is a path
from $x$ to $y$ in $G-C$ of order at least 3, then we call
$\overrightarrow{C}[z_i,z_{i+1}]$ a \emph{best segment} of $C$ (with
respect to $H$). Since $G$ is 2-connected, we conclude that for any
component $H$ of $G-C$, there are at least two good (better, best)
segments of $C$ with respect to $H$ if $\nu(H)\geq 1$ ($\nu(H)\geq
2$, $\nu(H)\geq 3$ and $H$ is not a star, respectively). Note that
every good (better, best) segment has order at least 3 (4, 5,
respectively).

Now we consider a component $H$ of $G-C$. If $H$ is non-separable,
then $H$ is a $K_1$, a $K_2$ or 2-connected; if $H$ is separable,
then $H$ has at least two end-blocks. In the later case, we call an
end-block of $H$ removing the cut-vertex contained in the end-block
a \emph{branch} of $H$ (also, of $G-C$).

\begin{claim}\label{Cl7}
Let $H$ be a component of $G-C$ and $u\in V(H)$.
\begin{mathitem}
\item If $H$ is non-separable, then $H$ contains a path from
$u$ of order at least $\min\{\nu(H),$ $\lceil r/2\rceil\}$.
\item If $H$ is separable and $D$ is a branch of $H$ not
containing $u$, then $H$ contains a path from $u$ of order at least
$\min\{\nu(D)+1,\lceil r/2\rceil\}$.
\end{mathitem}
\end{claim}

\begin{proof}
We first claim that for any two vertices $u,v\in V(H)$,
$d_H(u)+d_H(v)\geq \lceil r/2\rceil$, unless $uv$ is a cut-edge of
$H$. Assume that $uv$ is not a cut-edge of $H$. Then $H$ contains a
path from $u$ to $v$ of order at least 3. Let
$N_C(\{u,v\})=\{z_1,z_2,\ldots,z_k\}$, where $z_i$, $1\leq i\leq k$,
are in order along $C$. If $z_i$ is joined to exactly one vertex of
$u,v$, then $\overrightarrow{C}[z_i,z_{i+1}]$ is a good segment of
$C$ with respect to $\{u,v\}$; if $z_i$ is adjacent to both $u$ and
$v$, then $\overrightarrow{C}[z_i,z_{i+1}]$ is a best segment with
respect to $\{u,v\}$. This implies that
$d_C(u)+d_C(v)\leq\lfloor(n-r)/2\rfloor$ and
\begin{align*}
d_H(u)+d_H(v)
    & =d(u)+d(v)-d_C(u)-d_C(v)\\
    & \geq2\cdot\left(\left\lceil\frac{n}{2}\right\rceil-s+1\right)
        -\left\lfloor\frac{n-r}{2}\right\rfloor\\
    & =\left\lceil\frac{n+r}{2}\right\rceil+\pa(n)+2-2s\\
    & \geq\left\lceil\frac{n}{2}\right\rceil
        +\left\lceil\frac{r}{2}\right\rceil
        +2-2s\geq\left\lceil\frac{r}{2}\right\rceil.
\end{align*}

Now we prove the claim.

(1) If $H$ contains only one or two vertices, then the assertion is
trivially true. So we assume that $\nu(H)\geq 3$. Let $u'$ be a
vertex in $H$ such that $d_H(u')$ is as small as possible. Thus
$d_H(v)\geq\lceil\lceil r/2\rceil/2\rceil$ for any vertex $v\in
V(H)\backslash\{u,u'\}$. By Lemma \ref{Le2}, $H$ contains a path
from $u$ of order at least $\min\{\nu(H),\lceil r/2\rceil\}$.

(2) Let $B$ be the end-block of $H$ containing $D$ and $b$ be the
cut-vertex of $H$ contained in $B$. If $D$ contains only two
vertices, then the assertion is trivially true. So we assume that
$\nu(D)\geq 3$, from which we can see that $B$ is 2-connected. Let
$u'$ be a vertex in $B-b$ such that $d_{H}(u')$ is as small as
possible. Thus every vertex in $V(B)\backslash\{b,u'\}$ has degree
at least $\lceil\lceil r/2\rceil/2\rceil$ in $B$. By Lemma
\ref{Le2}, $B$ contains a path from $b$ of order at least
$\min\{\nu(B),\lceil r/2\rceil\}$, and $H$ contains a path from $u$
of order at least $\min\{\nu(B),\lceil
r/2\rceil\}=\min\{\nu(D)+1,\lceil r/2\rceil\}$.
\end{proof}

Now we choose $D$ among all the non-separable components and
branches of $G-C$ such that the order of $D$ is as small as
possible. We set a parameter $a$ such that $a=0$ if $D$ is a
non-separable component, and $a=1$ if $D$ is a branch of $G-C$.

If $D$ is a branch of $G-C$, then let $H$ be the component of $G-C$,
and $B$ the end-block of $G-C$, containing $D$; if $D$ is a
component of $G-C$, then let $H=B=D$.

\begin{subcase}
  $\nu(D)=1$.
\end{subcase}

Let $v$ be the vertex in $D$. If $D=H$, then let $R=G-C-H$,
$X=N_C^+(H)$. If $D\neq H$, then let $y$ be a vertex in $H-B$,
$R=G-C-B-y$ and $X=N_C^+(H)\cup\{y\}$. Thus every component of $R$
is joined to at most one vertex in $X$. Moreover, we have
\begin{align*}
\nu(R)  & =\nu(G)-\nu(C)-1-2a\\
        & =m+n-s-n+r-1-2a\\
        & =m+r-s-2a-1,
\end{align*}
and
\begin{align*}
|X|=d_C(H)+a\geq
d_C(v)+a=d(v)\geq\left\lceil\frac{n}{2}\right\rceil-s+1.
\end{align*}
Let $G'=G[V(R)\cup X]$. Note that there is a path of order at least
$2+2a$ with an end-vertex in $C$ and all other vertices in $H$. We
have $r\geq 2+2a$, and
\begin{align*}
\nu(G') & =\nu(R)+|X|\\
        & \geq m+r-s-2a-1+\left\lceil\frac{n}{2}\right\rceil-s+1\\
        & =m+\left\lceil\frac{n}{2}\right\rceil+r-2s-2a\\
        & \geq m+\left\lceil\frac{n}{2}\right\rceil+2-2s\geq m.
\end{align*}

\begin{claim}\label{Cl8}
  $D\neq H$ or $d_C(H)\geq 3$.
\end{claim}

\begin{proof}
Assume that $D=H$ and $d_C(H)=2$. Since $d_C(H)=d(v)\geq\lceil
n/2\rceil-s+1$, we have $n\leq 8$. We claim that every component of
$G-C$ is an isolated vertex. Suppose on the contrary that there is a
component $H'$ of $G-C$ with order at least 2. Note that there are
at least two better segments of $C$ with respect to $H'$. We have
$\nu(C)\geq 6$, and $G[V(C)\cup V(H')]$ contains a $P_8$, a
contradiction. Thus as we claimed, every component of $G-C$ is an
isolated vertex.

Note that $\nu(R)=m+r-s-1$. Since $s\leq 3$ (when $n\leq 8$) and
$r\geq 2$, we have $\nu(R)\geq m-2$. If $\nu(R)\geq m$, then there
is a $C_m$ in $\overline{G'}$; if $\nu(R)=m-1$, then $r=s\leq 3$,
and one of the two vertices in $N_C^+(H)$ is nonadjacent to every
vertex in $R$, and there is a $C_m$ in $\overline{G'}$; if
$\nu(R)=m-2$, then $r=s-1\leq 2$, and both of the two vertices in
$N_C^+(H)$ are nonadjacent to every vertex in $R$, and there is a
$C_m$ in $\overline{G'}$. In any case we get a contradiction. So we
conclude that $D\neq H$ or $d_C(H)\geq 3$.
\end{proof}

By Claim \ref{Cl8}, we can see that $|X|\geq 3$.

If there is a cycle $C'$ in $R$ with order $r+\pa(r)$, then let $P$
be a path between $C$ and $C'$, and $C\cup P\cup C'$ will contain a
$P_n$, a contradiction. Thus we assume that $R$ contains no cycle of
order $r+\pa(r)$. Since
\begin{align*}
\nu(R)+1-\frac{3}{2}(r+\pa(r))
    & =m+r-s-2a-1+1-\frac{3}{2}(r+\pa(r))\\
    & \geq m-s-2a-\left\lceil\frac{r}{2}\right\rceil-\pa(r)\\
    & \geq 2n-2s-1\geq 0,
\end{align*}
by Lemma \ref{Le4}, there is a path in $\overline{R}$ of order at
least
\begin{align*}
p   & =\nu(R)+1-\frac{r+\pa(r)}{2}\\
    & =m+r-s-2a-1+1-\left\lceil\frac{r}{2}\right\rceil\\
    & =m+\left\lfloor\frac{r}{2}\right\rfloor-s-2a.
\end{align*}

Note that
\begin{align*}
p+2|X|-3
    & \geq m+\left\lfloor\frac{r}{2}\right\rfloor-s-2a+
        2\left(\left\lceil\frac{n}{2}\right\rceil-s+1\right)-3\\
    & =m+n+\pa(n)+\left\lfloor\frac{r}{2}\right\rfloor-3s-2a-1\\
    & \geq m+n+\pa(n)-3s-a.
\end{align*}
We can see that $p+2|X|-3\geq m$, when $n\geq 9$, unless $n=11$ or
$12$ and $a=1$. If $n\leq 8$, then noting that $|X|\geq 3$, we also
have
\begin{align*}
p+2|X|-3\geq m+\left\lfloor\frac{r}{2}\right\rfloor-s-2a+3\geq
m-s+3\geq m.
\end{align*}
By Lemma \ref{Le7}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\noindent\textbf{Petty Case.} $n=11$ or $12$ and $a=1$.

We claim that every component of $G-C$ is a $K_1$, $K_2$, $K_3$ or a
star $K_{1,k}$. Suppose the contrary that there is a component $H'$
of order at least 4 which is not a star. Since there are at least
two best segments of $C$ with respect to $H'$, we can see that
$\nu(C)\geq 8$. Note that there is a path of order at least 5 with
one end-vertex in $C$ and all other vertices in $H'$. This implies
that $G[V(C)\cup V(H')]$ contains a $P_{12}$, a contradiction. Thus
as we claimed, every component of $G-C$ is a $K_1$, $K_2$, $K_3$ or
a star $K_{1,k}$.

Since $H$ is not a $K_1$, $K_2$ or $K_3$, we conclude that $H$ is a
star. Now we choose a component $H'$ of $G-C$ that is a maximum star
of $G-C$, and let $u'$ be the center of $H'$, $v'$ and $y'$ be two
end-vertices of $H'$. Let $R'=G-C-\{u',v',y'\}$,
$X'=N_C^+(H')\cup\{y'\}$ and $G''=G[V(R')\cup X']$. By the analysis
above, we have
\begin{align*}
\nu(R')\geq m+r-s-3 \mbox{ and }
|X'|\geq\left\lceil\frac{n}{2}\right\rceil-s+1.
\end{align*}

Since $\nu(R')\geq m+r-s-3\geq 2n+2-s\geq 20$. If $G-C$ has at least
three components, then $R'$ is disconnected; if $G-C$ has exactly
two components, then $H'$ is a star with at least 4 vertices, and
$R'$ is disconnected; if $G-C$ consists of only one component $H'$,
then $R'=H'-\{u',v',y'\}$ is empty, and thus disconnected. Thus in
any case, $\overline{R'}$ is connected.

Let $H''$ be a component of $R'$ with the maximum order. If
$\nu(H'')\leq\lceil\nu(R')/2\rceil$, then every vertex of $R'$ has
degree at least $\lfloor\nu(R')/2\rfloor$ in $\overline{R'}$. By
Lemma \ref{Le2}, $R'$ contains a Hamilton path. If
$\nu(H'')\geq\lceil\nu(R')/2\rceil+1$, then $H''$ is a star with at
least 4 vertices. Let $u''$ be the center of the star. Then every
vertex in $V(R')\backslash\{u''\}$ has degree at least
$\lceil\nu(R')/2\rceil$ in $\overline{R'-u''}$. By Lemma \ref{Le2},
$\overline{R'-u''}$ contains a Hamilton cycle and $\overline{R'}$
contains a Hamilton path. In any case $R'$ contains a path of order
at least $p'=\nu(R')$. Thus we have
\begin{align*}
p'+2|X'|-3\geq\nu(R')+|X'|\geq m.
\end{align*}

By Lemma \ref{Le7}, $\overline{G''}$ contains a $C_m$, a
contradiction.

\begin{subcase}
  $\nu(D)=2$.
\end{subcase}

Let $v,v'$ be the two vertices in $D$. If $D=H$, then let $R=G-C-H$,
$X_1=N_C^+(H)$, $X_2=N_C^-(H)$. If $D\neq H$, then let $y$ be a
vertex in $H-B$, let $R=G-C-B-y$, $X_1=N_C^+(H)\cup\{y\}$,
$X_2=N_C^-(H)\cup\{y\}$. Thus every component of $R$ is joined to at
most one vertex in $X_i$, $i=1,2$, and
\begin{align*}
\nu(R)  & =\nu(G)-\nu(C)-2-2a\\
        & =m+n-s-n+r-2-2a\\
        & =m+r-s-2a-2.
\end{align*}
Let $X=X_1\cup X_2$ and $G'=G[V(R)\cup X]$. Note that there is a
path of order at least $3+3a$ with an end-vertex in $C$ and all
other vertices in $H$. We have that $r\geq 3+3a$.

Let $N_C(H)=\{z_1,z_2,\ldots,z_k\}$, where $z_i$, $1\leq i\leq k$,
are in order along $C$. Since there are at least two better
segments, we have $|X_1\backslash X_2|=|X_2\backslash X_1|\geq 2$.
For any vertex $z_i\in N_C(H)$: if $z_i$ is adjacent to exactly one
vertex in $\{v,v'\}$, then $\overrightarrow{C}[z_i,z_{i+1}]$ is a
good segment; if $z_i$ is adjacent to both $v$ and $v'$, then
$\overrightarrow{C}[z_i,z_{i+1}]$ is a better segment. This implies
that
\begin{align*}
|X| & \geq d_C(v)+d_C(v')+a\\
    & \geq 2\left(\left\lceil\frac{n}{2}\right\rceil-s+1-1-a\right)+a\\
    & =n+\pa(n)-2s-a,
\end{align*}
and
\begin{align*}
\nu(G') & =\nu(R)+|X|\\
        & \geq m+r-s-2a-2+n+\pa(n)-2s-a\\
        & \geq m+3+3a-s-2a-2+n+\pa(n)-2s-a\\
        & \geq m+n+\pa(n)+1-3s\geq m.
\end{align*}

Since there are at least two better segments of $C$ with respect to
$H$, $\nu(C)\geq 6$. Thus there is a path in $G[V(C)\cup V(H)]$ of
order at least 8, which implies that $n\geq 9$.

\begin{claim}\label{Cl9}
  $D\neq H$ or $d_C(H)\geq 3$.
\end{claim}

\begin{proof}
Assume that $D=H$ and $d_C(H)=2$. Note that the two segments of $C$
with respect to $H$ are both better. Since $d_C(H)\geq
d(v)-1\geq\lceil n/2\rceil-s$, we have $n\leq 12$. We claim that
every component of $R$ has order at most $3$. Suppose on the
contrary that there is a component $H'$ of $G-C$ that has order at
least 4. Note that $H'$ is not a star. There are at least two best
segments of $C$ with respect to $H'$, which implies that $\nu(C)\geq
8$. Recall that $H'$ is not a star and has order at least 4. We can
see that there is a path of order at least 5 with one end-vertex in
$C$ and all other vertices in $H'$. Thus $G[V(C)\cup V(H')]$
contains a $P_{12}$, a contradiction. Thus as we claimed, every
component of $R$ has order 2 or 3.

Note that $\nu(R)=m+r-s-2$. Since $s\leq 4$ (when $n\leq 12$) and
$r\geq 3$, we have $\nu(R)\geq m-3$. If $\nu(R)\geq m$, then by
Lemma \ref{Le3} there is a $C_m$ in $\overline{G'}$; if $\nu(R)=m-1$
or $m-2$, then we have $r\leq s+1\leq 5$, and one of the two
vertices in $N_C^+(H)$ ($N_C^-(H)$) is nonadjacent to every vertex
in $R$, and there is a $C_m$ in $\overline{G'}$; if $\nu(R)=m-3$,
then $r=s-1\leq 3$, and every vertex in $N_C^+(H)$ and $N_C^-(H)$ is
nonadjacent to every vertex in $R$, and there is a $C_m$ in
$\overline{G'}$. In any case, we get a contradiction. So we conclude
that $D\neq H$ or $d_C(H)\geq 3$.
\end{proof}

By Claim \ref{Cl9}, we have $|X_1|=|X_2|\geq 3$.

If there is a cycle in $R$ of order $r+\pa(r)$, then there will be a
path of order at least $n$ in $G$. Thus we assume that $R$ contains
no cycle of order $r+\pa(r)$. Since
\begin{align*}
\nu(R)+1-\frac{3}{2}(r+\pa(r))
    & =m+r-s-2-2a+1-\frac{3}{2}(r+\pa(r))\\
    & \geq m-s-2a-\left\lceil\frac{r}{2}\right\rceil-\pa(r)-1\\
    & \geq 2n-2s-2\geq 0,
\end{align*}
by Lemma \ref{Le4}, there is a path in $\overline{R}$ of order at
least
\begin{align*}
p   & =\nu(R)+1-\frac{r+\pa(r)}{2}\\
    & =m+r-s-2-2a+1-\left\lceil\frac{r}{2}\right\rceil\\
    & =m+\left\lfloor\frac{r}{2}\right\rfloor-s-2a-1.
\end{align*}

Note that
\begin{align*}
p+2|X|-5
    & \geq m+\left\lfloor\frac{r}{2}\right\rfloor-s-2a-1+2(n+\pa(n)-2s-a)-5\\
    & =m+2n+2\pa(n)+\left\lfloor\frac{r}{2}\right\rfloor-5s-4a-6\\
    & \geq m+2n+2\pa(n)-5s-7.
\end{align*}
We can see that $p+2|X|-5\geq m$, when $n\geq 13$. If $n\leq 12$,
then noting that $d_C(H)+a\geq 3$ and $|X|\geq 5$, we also have
\begin{align*}
p+2|X|-5\geq m+\left\lfloor\frac{r}{2}\right\rfloor-s-2a-1+5 \geq
m-s+5\geq m.
\end{align*}

By Lemma \ref{Le8}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{subcase}
  $3\leq\nu(D)\leq\lceil r/2\rceil-1$.
\end{subcase}

In this case, $r\geq 7$. If $D=H$, then let $R=G-C-H$,
$X_1=N_C^+(H)$ and $X_2=N_C^-(H)$. If $D\neq H$, then let $y$ be a
vertex in $H-B$ which is not a cut-vertex of $H-B$, let $R=G-C-B-y$,
$X_1=N_C^+(H)\cup\{y\}$ and $X_2=N_C^-(H)\cup\{y\}$. Thus every
component of $R$ is joined to at most one vertex in $X_i$, $i=1,2$,
and
\begin{align*}
\nu(R)  & =\nu(G)-\nu(C)-\nu(D)-2a\\
        & \geq m+n-s-n+r-\left\lceil\frac{r}{2}\right\rceil+1-2a\\
        & =m+\left\lfloor\frac{r}{2}\right\rfloor+1-s-2a.
\end{align*}
Clearly, every component of $R$ has order at least 2, and
\begin{align*}
\left\lceil\frac{3\nu(R)}{2}\right\rceil+4
    & \geq\left\lceil\frac{3(m+\lfloor r/2\rfloor+1-s-2a)}{2}\right\rceil+4\\
    & \geq m+\left\lceil\frac{m+3(3+1-s-2a)}{2}\right\rceil+4\\
    & \geq m+\left\lceil\frac{2n+15-3s}{2}\right\rceil\geq m.
\end{align*}

Let $X=X_1\cup X_2$ and $G'=G[V(G-B)\backslash N_C(H)]$. Since there
are at least two best segments with respect to $H$, we have
$|X_1\backslash X_2|=|X_2\backslash X_1|\geq 2$. Let $v$ be a vertex
in $D$.

Since $R$ contains no cycle of length $r+\pa(r)$ and
\begin{align*}
\nu(R)+1-\frac{3}{2}(r+\pa(r))
    & =m+\left\lfloor\frac{r}{2}\right\rfloor+1-s-2a+1
        -3\cdot\left\lceil\frac{r}{2}\right\rceil\\
    & \geq m+2-r-2\pa(r)-s-2a\\
    & \geq 2n+3-2s+\pa(n)+2-2\pa(r)-s-2a\\
    & \geq 2n+\pa(n)+1-3s\geq 0,
\end{align*}
$\overline{R}$ contains a path of order at least
\begin{align*}
p   & =\nu(R)+1-\frac{r+\pa(r)}{2}\\
    & \geq m+\left\lfloor\frac{r}{2}\right\rfloor+1-s-2a+1
        -\left\lceil\frac{r}{2}\right\rceil\\
    & =m+2-s-\pa(r)-2a.
\end{align*}

\begin{claim}\label{Cl10}
  $D\neq H$ or $d_C(H)\geq 3$.
\end{claim}

\begin{proof}
Assume that $D=H$ and $d_C(H)=2$. Thus
\begin{align*}
d_D(v)\geq\left\lceil\frac{n}{2}\right\rceil-s+1-2
=\left\lceil\frac{n}{2}\right\rceil-s-1,
\end{align*}
and
\begin{align*}
\nu(D)\geq 1+d_D(v)\geq\left\lceil\frac{n}{2}\right\rceil-s \geq
s-2\geq\left\lceil\frac{r}{2}\right\rceil-1.
\end{align*}
This implies that $\lceil r/2\rceil=s-1$, $\nu(D)=\lceil
r/2\rceil-1$, and $d_D(v)=\nu(D)-1$. Note that in this case every
vertex in $D$ has degree $\nu(D)-1$, and thus $D$ is a clique.

If every vertex in $N_C^+(H)$ is joined to some component of $G-C$,
then by Claim \ref{Cl7}, we can find a path from the cycle $C$,
component $H$ and the two components joined to the two vertices in
$N_C^+(H)$, of order at least
\begin{align*}
\nu(C)+3\nu(D)
    & =\nu(C)+3\cdot\left(\left\lceil\frac{r}{2}\right\rceil-1\right)\\
    & = n-r+r+\pa(r)+\left\lceil\frac{r}{2}\right\rceil-3\\
    & \geq n,
\end{align*}
a contradiction. Thus there is a vertex $v'$ in $N_C^+(H)$ that is
not joined to every component of $G-C$. Let $G''=G-C$.

Since $\lceil r/2\rceil=s-1$ and $r\geq 7$, we can see that $r\geq
s+1$. Thus
\begin{align*}
\nu(G'')=\nu(G)-\nu(C)\geq m+n-s-n+r=m+r-s\geq m.
\end{align*}
Note that in this case, $\overline{G''-H}=\overline{R}$ contains a
path of order at least $p\geq m+2-s-\pa(r)\geq m+3-r-\pa(r)$ and
\begin{align*}
p+2\nu(H)-1
    & \geq m+3-r-\pa(r)+2\cdot\left(\left\lceil\frac{r}{2}\right\rceil-1\right)-1\\
    & =m+3-r-\pa(r)+r+\pa(r)-2-1\\
    & =m.
\end{align*}
Since
\begin{align*}
\nu(R)\geq m+\left\lfloor\frac{r}{2}\right\rfloor+1-s=m-\pa(r)
\geq\left\lceil\frac{m}{2}\right\rceil,
\end{align*}
by Lemma \ref{Le5}, $\overline{G''}$ contains a $C_m$, and
$\overline{G}$ contains a $W_m$ with the hub $v'$, a contradiction.
\end{proof}

By Claim \ref{Cl10}, $|X_1|=|X_2|\geq 3$. If $D\neq H$, then since
there are at least two best segments with respect to $H$, we can see
that $\nu(C)\geq 8$; if $D=H$ and $d_C(H)\geq 3$, noting that at
least two segments of $C$ with respect to $H$ are best, we have
$\nu(C)\geq 10$. Since $\nu(C)= n-r$ and $r\geq 7$, we conclude that
$n\geq 15$.

Let $H'$ be a component of $R$, and let $W$ be the union of $X$ and
the set of vertices in $V(C)\backslash N_C(H)$ not joined to $H'$.
For any two vertices $x,y$ with $xy\in E(C)$: if one of $x,y$ is in
$N_C(H)$, then the other one will be in $X\subset W$; if none of
them is in $N_C(H)$, then at least one of them will not be joined to
$H'$, otherwise there will be a cycle longer than $C$. This implies
that $|W|\geq \lceil(n-r)/2\rceil+a=q$.

Since
\begin{align*}
\nu(R)+q-1
    & \geq m+\left\lfloor\frac{r}{2}\right\rfloor+1-s-2a
        +\left\lceil\frac{n-r}{2}\right\rceil+a-1\\
    & \geq m+\left\lfloor\frac{n}{2}\right\rfloor-s-a\geq m,
\end{align*}
($n\geq 14$) and
\begin{align*}
p+2q-5
    & \geq m+2-s-\pa(r)-2a+2\cdot\left(\left\lceil\frac{n-r}{2}\right\rceil+a\right)-5\\
    & =m+n-r-s-3+\pa(n-r)-\pa(r)\\
    & =m+n-3s-1+\pa(n)+\pa(n-r)-\pa(r)\\
    & \geq m+n-3s-1,
\end{align*}
we can see that $p+2q-5\geq m$, unless $n=15$, $s=5$ and $r=7$.

\noindent\textbf{Petty Case.} $n=15$, $s=5$ and $r=7$.

In this case, $\nu(C)=8$ which implies that $D\neq H$. It is easy to
find a path with two end-vertices in $C$ and all internal vertices
in $H$ of order at least 7. Thus $\nu(C)\geq 12$, a contradiction.

By Lemma \ref{Le9}, $\overline{G'}$ contains a $C_m$, a
contradiction.

\begin{subcase}
  $\nu(D)\geq\max\{\lceil r/2\rceil,3\}$.
\end{subcase}

In this case, there is a path of order at least 4 with an end-vertex
in $C$ and all other vertices in $H$. Thus we have $r\geq 4$. Let
$H'$ be an arbitrary component of $G-C$ and $u\in V(H')$. By Claim
\ref{Cl7}, $H'$ contains a path from $u$ of order at least $\lceil
r/2\rceil$. Thus for any edge $xy\in E(C)$, either $x$ or $y$ is not
joined to any components of $G-C$, otherwise there will be a $P_n$
in $G$. Moreover, if $r$ is odd and $x$ is joined to some component,
say $H'$, of $G-C$, then $x^{++}$ will not be joined to any
component of $G-C$ other than $H'$ as well.

\begin{subsubcase}
Every component of $G-C$ has order less than $r$.
\end{subsubcase}

Let $v$ be a vertex in $N_C^+(H)$, and let $G'=G[V(G-C)\cup
N_C^+(H)\backslash\{v\}]$. Note that $v$ is nonadjacent to every
vertex in $G'$, and every component of $G'$ has order at most
\begin{align*}
r-1\leq 2s-\pa(n)-2-1\leq\left\lceil\frac{n}{2}\right\rceil
\leq\left\lfloor\frac{m}{2}\right\rfloor.
\end{align*}
Let $u$ be a vertex in $H$. Since
\begin{align*}
d_C(H)\geq d_C(u)\geq d(u)-\nu(H)+1\geq d(u)+2-r,
\end{align*}
and
\begin{align*}
\nu(G') & =\nu(G)-\nu(C)+d_C(H)-1\\
        & \geq m+n-s-n+r+d(v)+1-r\\
        & \geq m-s+\left\lceil\frac{n}{2}\right\rceil-s+1+1\\
        & = m+\left\lceil\frac{n}{2}\right\rceil+2-2s\geq m,
\end{align*}
by Lemma \ref{Le3}, there is a $C_m$ in $\overline{G'}$, a
contradiction.

\begin{subsubcase}
There is a component of $G-C$ of order at least $r$.
\end{subsubcase}

Let $H'$ be a component of $G-C$ with order at least $r$. We claim
that there is a vertex $u$ in $H'$ with $d_{H'}(u)\leq\lceil
r/2\rceil-1$. Suppose the contrary that every vertex of $H'$ has
degree at least $\lceil r/2\rceil$ in $H'$. If $H'$ is 2-connected,
then by Lemma \ref{Le2}, there is a cycle of order at least $r$ in
$H'$, and $G$ will contain a $P_n$; if $G$ is separable, letting
$B'$ be any end-block of $H'$, $b'$ be the cut-vertex of $H'$
contained in $B'$, and $u'$ be any vertex in
$V(B')\backslash\{b'\}$, then there is a path from $b'$ to $u'$ of
order at least $\lceil r/2\rceil+1$. Thus $G$ will contain a $P_n$
as well. So we assume that there is a vertex $u$ in $H'$ with
$d_{H'}(u)\leq\lceil r/2\rceil-1$.

Let $v$ be a vertex in $N_C^+(H')$, $X=N_C^+(H')\backslash\{v\}$. If
$r$ is odd, then let $\overrightarrow{C}[z,z']$ be a better segment
of $C$ with respect to $H'$ not containing $v$, and we add $z^{++}$
to $X$. Let $G'=G[V(G-C)\cup X]$. Note that $v$ is nonadjacent to
every vertex in $G'$, and there are no edges between $G-C$ and $X$.

Since
\begin{align*}
d_C(H') & \geq d_C(u)=d(u)-d_{H'}(u)\\
        & \geq\left\lceil\frac{n}{2}\right\rceil-s+1
            -\left\lceil\frac{r}{2}\right\rceil+1\\
        & =\left\lceil\frac{n}{2}\right\rceil+2
            -\left\lceil\frac{r}{2}\right\rceil-s,
\end{align*}
we have
\begin{align*}
|X|=d_C(H)-1+\pa(r)\geq\left\lceil\frac{n}{2}\right\rceil+1
-\left\lfloor\frac{r}{2}\right\rfloor-s
\end{align*}
and
\begin{align*}
\nu(G') & =\nu(G)-\nu(C)+|X|\\
        & \geq m+n-s-n+r+\left\lceil\frac{n}{2}\right\rceil+1
            -\left\lfloor\frac{r}{2}\right\rfloor-s\\
        & \geq m-s+\left\lceil\frac{r}{2}\right\rceil
            +\left\lceil\frac{n}{2}\right\rceil-s+1\\
        & \geq m+\left\lceil\frac{n}{2}\right\rceil+3-2s\geq m.
\end{align*}

Since $G-C$ contains no cycle of length $r+\pa(r)$ and
\begin{align*}
\nu(G-C)+1-\frac{3}{2}(r+\pa(r))
    & =m+r-s+1-3\cdot\left\lceil\frac{r}{2}\right\rceil\\
    & \geq m-\left\lceil\frac{r}{2}\right\rceil-\pa(r)-s\\
    & \geq 2n-2s\geq 0,
\end{align*}
$\overline{G-C}$ contains a path of order at least
\begin{align*}
p   & =\nu(G-C)+1-\frac{r+\pa(r)}{2}\\
    & =m+r-s+1-\left\lceil\frac{r}{2}\right\rceil\\
    & =m+\left\lfloor\frac{r}{2}\right\rfloor+1-s.
\end{align*}
Clearly $|X|\geq 1$. If $\lfloor r/2\rfloor\geq s-2$, then
\begin{align*}
p+2|X|-1
    & \geq m+\left\lfloor\frac{r}{2}\right\rfloor+1-s+2-1\\
    & \geq m+s-2+1-s+2-1\\
    & =m.
\end{align*}
If $\lfloor r/2\rfloor\leq s-3$, then
\begin{align*}
p+2|X|-1
    & \geq m+\left\lfloor\frac{r}{2}\right\rfloor+1-s+
        2\cdot\left(\left\lceil\frac{n}{2}\right\rceil+1
        -\left\lfloor\frac{r}{2}\right\rfloor-s\right)-1\\
    & =m+n+\pa(n)+2-\left\lfloor\frac{r}{2}\right\rfloor-3s\\
    & \geq m+n+\pa(n)+5-4s\geq m.
\end{align*}
Since
\begin{align*}
\nu(G-C)=m+r-s\geq\left\lceil\frac{m}{2}\right\rceil,
\end{align*}
by Lemma \ref{Le5}, there is a $C_m$ in $\overline{G'}$, a
contradiction.

The proof is complete.\hfill$\Box$

%
\section{Remarks}
%

A \emph{linear forest} is a forest such that every component of it
is a path. From our main result of the paper, we can conclude the
following result.

\begin{corollary}
Let $n\geq 2$, $m\geq 2n+1$ and $F$ be a linear forest on $m$
vertices. Then $$R(P_n,K_1\vee F)=t(n,m).$$
\end{corollary}

\begin{proof}
Note that the graph constructed at the beginning of Section 3
contains no $P_n$ and its complement contains no $K_1\vee F$. We
conclude that $R(P_n,K_1\vee F)\geq t(n,m)$. On the other hand,
since $K_1\vee F$ is a subgraph of $W_m$, we have $R(P_n,K_1\vee
F)\leq R(P_n,W_m)\leq t(n,m)$.
\end{proof}

For the case $F$ is an empty graph, the above formula gives the
Ramsey numbers of paths versus stars when $m\geq 2n+1$. In fact,
Parsons \cite{Parsons} gave all the values of the path-star Ramsey
numbers by a recursive formula.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors are very grateful to Professor Yunqing Zhang for
providing them the paper \cite{Zhang}. The research is supported by
NSFC (No. 11271300), the Doctorate Foundation of Northwestern
Polytechnical University (No. cx201202 and No. cx201326) and the
project NEXLIZ - CZ.1.07/2.3.00/30.0038, which is co-financed by the
European Social Fund and the state budget of the Czech Republic.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}

\begin{thebibliography}{10}

\bibitem{Bakoro_Surahmat}
E.T. Baskoro and Surahmat. \newblock The Ramsey number of paths with
respect to wheels. \newblock \emph{Discrete Math.}, 294:275--277,
2005.

\bibitem{Bondy_Murty}
J.A.~Bondy and U.S.R.~Murty. \newblock Graph Theory with
Applications. \newblock Macmillan, London and Elsevier, New York,
1976.

\bibitem{Chen_Zhang_Zhang}
Y. Chen, Y. Zhang and K. Zhang. \newblock The Ramsey numbers of
paths versus wheels. \newblock \emph{Discrete Math.}, 290:85--87,
2005.

\bibitem{Dirac}
G.A. Dirac. \newblock Some theorems on abstract graphs. \newblock
\emph{Proc. London. Math. Soc.}, 2:69--81, 1952.

\bibitem{Erdos}
P. Erd\H{o}s. \newblock Some remarks on the theory of graphs.
\newblock \emph{Bull. Amer. Math. Soc.}, 53:292--294, 1947.

\bibitem{Erdos_Gallai}
P. Erd\H{o}s and T. Gallai. \newblock On maximal paths and circuits
of graphs. \newblock \emph{Acta Math. Acad. Sci. Hungar.},
10:337--356, 1959.

\bibitem{Fan}
G.~Fan. \newblock New sufficient conditions for cycles in graphs.
\newblock \emph{J. Combin. Theory, Ser. B}, 37:221--227, 1984.

\bibitem{Faudree_Lawrence_Parsons_Schelp}
R.J. Faudree, S.L. Lawrence, T.D. Parsons and R.H. Schelp. \newblock
Path-cycle Ramsey numbers. \newblock \emph{Discrete Math.},
10:269--277, 1974.

\bibitem{Gerencser_Gyarfas}
L. Gerencs\'{e}r and A. Gy\'{a}rf\'as. \newblock On Ramsey-type
problems. \newblock \emph{Ann. Univ. Sci. Budapest. E\"{o}tv\"{o}s
Sect. Math.}, 10:167--170, 1967.

\bibitem{Parsons}
T.D. Parsons. \newblock Path-star Ramsey numbers. \newblock \emph{J.
Combin. Theory, Ser. B}, 17:51--58, 1974.

\bibitem{Salman_Broersma}
A.N.M. Salman and H.J. Broersma. \newblock On Ramsey numbers for
paths versus wheels. \newblock \emph{Discrete Math.}, 307:975--982,
2007.

\bibitem{Zhang}
Y. Zhang. \newblock On Ramsey numbers of short paths versus large
wheels. \newblock \emph{Ars Combin.}, 89:11--20, 2008.

\end{thebibliography}

\end{document}
