1 Introduction
Ramsey theory is concerned with the emergence of order in large and complex structures. One of its central concepts is the Ramsey number, which captures the threshold at which a certain structure must appear.
Given two graphs G and H, the Ramsey number
$R(G,H)$
is defined as the smallest positive integer N such that every graph
$\Gamma $
on N vertices either contains G as a subgraph or its complement
$\overline {\Gamma }$
contains H as a subgraph. Equivalently,
$R(G,H)$
is the smallest integer N such that in every red–blue edge-colouring of the complete graph
$K_N$
, we can always find either a red copy of G or a blue copy of H.
We use
$C_n$
to denote the cycle on n vertices, and
$W_n$
to denote the graph obtained by adding an extra vertex to
$C_n$
and connecting it to every vertex on the cycle. We often refer to such a wheel by the parity of the order of its outer cycle. That is, an even wheel is a wheel of odd order and an odd wheel is a wheel of even order. As cycles and wheels are basic graph classes in graph theory, the Ramsey number
$R(C_n,W_\ell )$
has attracted considerable attention since the last century. In 1983, Burr and Erdős [Reference Burr and Erdős5] initiated the study of cycle–wheel Ramsey numbers and proved that
$R(C_3,W_{\ell })=2\ell +1$
for
$\ell \ge 5$
. However, when
$C_3$
is replaced by
$C_4$
, the problem becomes significantly more complex. In 2014, Zhang et al. [Reference Zhang, Broersma and Chen19] showed that
$R(C_4,W_{\ell })=R(C_4,K_{1,\ell })$
for
$\ell \ge 6$
. The exact value of the latter is only known in certain special cases, and the general upper bound problem encompasses a $100 conjecture of Erdős [Reference Burr, Erdős, Faudree, Rousseau, Schelp, Andersen, Jakobsen, Thomassen, Toft and Vestegaard6]. In addition to the aforementioned studies focused on small cycles (
$C_3$
and
$C_4$
), substantial progress has been made on Ramsey numbers for more general cycle–wheel combinations. For Ramsey numbers involving odd cycles and large wheels, a series of results were obtained by Zhang et al. [Reference Zhang, Zhang and Chen21], Sanhueza-Matamala [Reference Sanhueza-Matamala13] and Alweiss [Reference Alweiss1]. For even cycles and odd wheels, when
$n<\ell <3n/2$
, Zhang et al. [Reference Zhang, Broersma and Chen20] also determined the exact value of
$R(C_n,W_{\ell })$
.
When the order of the cycle is large relative to that of the wheel, the parity of the wheel plays a crucial role in determining the Ramsey number. For clarity, we consider odd wheels
$W_{2m+1}$
and even wheels
$W_{2m}$
separately. In this context, Surahmat et al. [Reference Baskoro and Tomescu16, Reference Baskoro and Tomescu17] proposed the following two conjectures.
Conjecture 1.1. If
$n\ge 2m+1\ge 3$
and
$(n,m)\ne (3,1)$
, then
$R(C_n,W_{2m+1})=3n-2$
.
Conjecture 1.2. If
$n\ge 2m\ge 4$
and
$(n,m)\not =(4,2)$
, then
$R(C_n,W_{2m})=2n-1$
.
Subsequent research has delved deeply into these conjectures in an effort to verify them.
Regarding the odd wheel
$W_{2m+1}$
, when does the equality
$R(C_n,W_{2m+1})=3n-2$
hold? In 2008, Surahmat et al. [Reference Baskoro and Tomescu17] proved that this formula holds when
$m\ge 2$
and
$n>5m-2$
. In 2010, Shi [Reference Shi14] improved the bound to
$n>70$
or
$n\ge 3m+3$
. Later that same year, Zhang et al. [Reference Zhang, Chen and Cheng18] further reduced the requirement to
$n\ge 20$
. Ultimately, in 2012, Chen et al. [Reference Chen, Cheng, Ng and Zhang8] completely resolved Conjecture 1.1.
As for the even wheel
$W_{2m}$
, when does the equality
$R(C_n,W_{2m})=2n-1$
hold? In 2006, Surahmat et al. [Reference Baskoro and Tomescu16] proved that the formula holds when
$n\ge 5m-1$
. In 2009, Chen et al. [Reference Chen, Cheng, Miao and Ng7] improved the bound to
$n\ge 3m+1$
. Later, in 2015, Zhang et al. [Reference Zhang, Broersma and Chen20] further lowered the requirement to
$n\ge 2m+502$
. Combining all known results, it follows that the statement
$R(C_n,W_{2m})=2n-1$
holds whenever
$m \ge 2$
and
$n\ge 2m+\min \{m+1,502\}$
, thereby almost resolving Conjecture 1.2.
Extending these results, Sudarsana [Reference Sudarsana15] studied Ramsey numbers of large cycles versus disjoint unions of multiple wheels. We use
$tW_{\ell }$
to denote the disjoint union of t copies of the wheel
$W_{\ell }$
. Sudarsana [Reference Sudarsana15] proposed the following conjecture.
Conjecture 1.3. For
$t\ge 1$
and
$m\ge 2$
, there exists an integer
$n_0$
such that
$$ \begin{align*} R(C_n,tW_{2m})=2n+t-2 \quad \text{and} \quad R(C_n,tW_{2m+1})=3n+t-3 \quad \mbox{ for all } n\ge n_0. \end{align*} $$
In our paper ‘Ramsey numbers of cycles versus multiple wheels’ (submitted), we proved that Sudarsana’s conjecture holds in the case of even wheels.
Theorem 1.4. For
$t\ge 1$
and
$m\ge 2$
, if
$n\ge 4tm$
, then
$R(C_n, tW_{2m})=2n+t-2$
.
The main result of this paper confirms that Sudarsana’s conjecture also holds for odd wheels.
Theorem 1.5. For
$t\ge 2$
and
$m\ge 1$
, if
$n\ge (6m+3)t-6m+999$
, then
$$ \begin{align*}R(C_n,tW_{2m+1})=3n+t-3.\end{align*} $$
For
$t=1$
,
$n\ge 2m+1$
and
$(n,m)\ne (3,1)$
, Chen et al. [Reference Chen, Cheng, Ng and Zhang8] had already established that
$R(C_n,W_{2m+1})=3n-2$
. Therefore, Conjecture 1.3 proposed by Sudarsana is now fully confirmed.
The structure of this paper is as follows: we present six useful lemmas in Section 2 and give a complete proof of Theorem 1.5 in Section 3.
To complete this section, we introduce additional notation. We use
$[n]$
to denote the set
$\{1,2,\ldots ,n\}$
. The symbols
$|G|$
,
$\delta (G)$
,
$\Delta (G)$
,
$\omega (G)$
and
$\chi (G)$
denote respectively the number of vertices, the minimum degree, the maximum degree, the number of connected components and the chromatic number of a graph G. The circumference of a graph G, denoted by
$c(G)$
, is the length of the longest cycle in G, while the girth of G, denoted by
$g(G)$
, is the length of the shortest cycle in G. The connectivity
$\kappa (G)$
of a graph G refers to the minimum number of vertices whose removal results in a disconnected graph. The closure
$\text {cl}(G)$
of a graph
$G=(V,E)$
is the graph obtained by recursively adding edges between nonadjacent vertex pairs whose degree sum is at least
$|V|$
, until no such pair remains. This process results in a unique graph, regardless of the order in which the edges are added. The chromatic surplus of G refers to the number of vertices in the smallest colour class among all proper colourings of G using
$\chi (G)$
colours. Given a subset
$U\subseteq V(G)$
, we write
$G[U]$
for the subgraph of G induced by U. The graph obtained by removing the vertex set U and all incident edges from G is denoted by
$G-U$
; if
$U=\{u\}$
, we simply write
$G-u$
. For disjoint subsets
${U_1,U_2\subseteq V(G)}$
, the notation
$G[U_1,U_2]$
denotes the subgraph induced by all edges with one endpoint in
$U_1$
and the other in
$U_2$
. The disjoint union of graphs G and H is denoted by
$G\cup H$
. For a subgraph H and a vertex u in H, let
$d_H(u)$
denote the number of neighbours of u in H. Notation and terminology not explicitly defined follow those in the textbook by Bondy and Murty [Reference Bondy and Murty3].
2 Useful lemmas
Lemma 2.1 (Dirac [Reference Dirac9]).
Let G be a
$2$
-connected graph of order
$n\ge 3$
with minimum degree
$\delta =\delta (G)$
. Then,
$c(G)\ge \min \{2\delta ,n\}$
.
Lemma 2.2 (Rosta [Reference Rosta12], Faudree and Schelp [Reference Faudree and Schelp10]).
We have
$R(C_n,C_{2m+1})=2n-1$
for
$n \ge 2m+1\ge 3$
and
$(n,m)\ne (3,1)$
.
Lemma 2.3 (Burr and Erdős [Reference Burr and Erdős5], Greenwood and Gleason [Reference Greenwood and Gleason11]).
We have
$$ \begin{align*}R(C_3,W_{2m+1})= \begin{cases} 9 & \text{if } m=1, \\ 4m+3 & \text{if } m\ge 2. \end{cases}\end{align*} $$
Lemma 2.4 (Bondy and Chvátal [Reference Bondy and Chvátal2]).
A graph is Hamiltonian if and only if its closure is Hamiltonian.
Lemma 2.5 (Brandt et al. [Reference Brandt, Faudree and Goddard4]).
Let G be a nonbipartite graph of order n with
${\delta (G) \ge (n+2)/3}$
. Then, G is weakly pancyclic with girth
$3$
or
$4$
.
Lemma 2.6 (Brandt et al. [Reference Brandt, Faudree and Goddard4]).
Let G be a
$2$
-connected nonbipartite graph of order n with
$\delta (G) \ge n/4+250$
. Then, G is weakly pancyclic, unless its odd girth is
$7$
. In that case, G contains a cycle of every length from
$4$
up to its circumference, except possibly a cycle of length
$5$
.
3 Proof of Theorem 1.5
For the lower bound, consider the graph
$K_{n-1}\cup K_{n-1}\cup K_{n-1}\cup K_{t-1}$
. Clearly, it does not contain
$C_n$
as a subgraph. Its complement is the complete 4-partite graph
$K_{n-1,n-1,n-1,t-1}$
, which has chromatic surplus
$t-1$
. However, the graph
$tW_{2m+1}$
has chromatic number
$4$
and chromatic surplus t, and therefore cannot be contained as a subgraph in
$K_{n-1,n-1,n-1,t-1}$
. It follows that
$$ \begin{align*}R(C_n, tW_{2m+1})\ge 3n+t-3.\end{align*} $$
Let
$t\ge 2$
,
$m\ge 1$
and
$n\ge (6m+3)t-6m+999$
. Let G be a graph of order
${3n+t-3}$
. To establish the upper bound, assume for contradiction that G does not contain
$C_n$
as a subgraph and that its complement
$\overline {G}$
does not contain
$tW_{2m+1}$
as a subgraph. We shall derive a contradiction.
First, select as many vertex-disjoint copies of
$W_{2m+1}$
in the graph
$\overline {G}$
as possible and suppose that a total of x such copies are selected. By the assumption, we have
$x\le t-1$
. Next, remove all the vertices of these x disjoint copies of
$W_{2m+1}$
from G and denote the resulting graph by
$G'$
. By the maximality of x, the complement
$\overline {G'}$
contains no copy of
$W_{2m+1}$
.
We now proceed with the following sequence of claims.
Claim 1. We have
$|G'|\ge 3n-(2m+1)t+2m-1$
. Consequently,
$|G'|\ge 8n/3+332$
and
$|G'|\ge 16m+3012$
.
Proof. All three lower bounds follow from straightforward calculations:
$$ \begin{align*} |G'| & = |G|-x(2m+2)\\ & \ge |G|-(t-1)(2m+2)\\ & = (3n+t-3)-(t-1)(2m+2)\\ & = 3n-(2m+1)t+2m-1. \end{align*} $$
Since
$t\ge 2$
and
$n\ge (6m+3)t-6m+999$
, it follows that
$$ \begin{align*}3|G'|\ge 9n-(6m+3)t+6m-3\ge 8n+996.\end{align*} $$
Therefore,
$|G'|\ge 8n/3+332$
. Substituting
$n\ge (6m+3)t-6m+999\ge 6m+1005$
into the inequality above yields
$|G'|\ge 16m+3012$
.
Claim 2. We have
$\delta (G')\ge |G'|-2n+1$
,
$\delta (G')\ge |G'|/4+250$
and
$\delta (G')\ge n/2+1$
.
Proof. We first prove that
$\delta (G')\ge |G'|-2n+1$
. Suppose otherwise, that is,
$\delta (G')\le |G'|-2n$
. Then,
$\Delta (\overline {G'})=|G'|-1-\delta (G')\ge 2n-1$
. Let
$u_0$
be a vertex of minimum degree in
$G'$
and denote by
$G_0$
the subgraph induced by the set of nonneighbours of
$u_0$
in
$G'$
. Then,
$|G_0|\ge 2n-1$
. By Lemma 2.2, either
$G_0$
contains a copy of
$C_n$
as a subgraph or
$\overline {G_0}$
contains a copy of
$C_{2m+1}$
as a subgraph, which together with
$u_0$
would form a copy of
$W_{2m+1}$
in
$\overline {G'}$
. Both cases lead to a contradiction. Hence,
$\delta (G')\ge |G'|-2n+1$
.
To prove
$\delta (G')\ge |G'|/4+250$
, it suffices to show that
$|G'|-2n+1\ge |G'|/4+250$
, which is equivalent to proving
$3|G'|\ge 8n+996$
. Therefore, by Claim 1, we conclude that
$\delta (G')\ge |G'|/4+250$
. Since
$\delta (G')\ge |G'|-2n+1$
and
$|G'|\ge 5n/2$
, it follows that
$\delta (G')\ge n/2+1$
.
Claim 3.
$G'$
is nonbipartite.
Proof. Suppose, in contrast, that
$G'$
is bipartite. Then, its independence number satisfies
$\alpha (G')\ge |G'|/2$
. It follows from Claim 1 that
$\alpha (G')\ge 2m+2$
. Hence,
$\overline {G'}$
contains
$K_{2m+2}$
as a subgraph and thus also contains
$W_{2m+1}$
as a subgraph, which contradicts our assumption. Therefore,
$G'$
must be nonbipartite.
Claim 4.
$\kappa (G')\le 1$
.
Proof. Since
$|G'|\ge 4m+5$
, by Lemma 2.3, either
$G'$
contains
$C_3$
as a subgraph or
$\overline {G'}$
contains
$W_{2m+1}$
as a subgraph. The latter contradicts our assumption. Thus,
$g(G')=3$
.
Suppose
$\kappa (G')\ge 2$
. Then, by Lemma 2.1 and Claims 1 and 2, we have
$c(G')\ge \min \{2\delta (G'), |G'|\}\ge n$
.
Moreover, if
$\kappa (G')\ge 2$
, then by Lemma 2.6 and Claims 2 and 3, the graph
$G'$
is weakly pancyclic. Hence,
$G'$
contains
$C_n$
as a subgraph, which is again a contradiction. Therefore, we conclude that
$\kappa (G')\le 1$
.
Claim 5. There exist two vertices
$u_1$
and
$u_2$
in
$G'$
such that
$G'-\{u_1,u_2\}$
has at least three connected components.
Proof. By Claim 2,
$\delta (G')\ge |G'|/4+250\ge 250$
. Hence, every connected component of
$G'$
contains at least
$251$
vertices. From Claim 4, we have
$\kappa (G')\le 1$
. If
$\kappa (G')=0$
, then for any vertex
$u_1$
in
$G'$
, the graph
$G'-u_1$
has at least two connected components. If
$\kappa (G')=1$
, let
$u_1$
be a cut vertex of
$G'$
. Again,
$G'-u_1$
has at least two connected components.
If
$G'-u_1$
has at least three connected components, then for any vertex
$u_2$
in
$G'-u_1$
, the graph
$G'-\{u_1,u_2\}$
also has at least three connected components.
If
$G'-u_1$
has exactly two connected components and one of them is not 2-connected, let
$u_2$
be a cut vertex of that component. Then,
$G'-\{u_1,u_2\}$
has at least three connected components.
We now consider the case where
$G'-u_1$
has exactly two connected components and each component is 2-connected. Without loss of generality, let
$G_1$
and
$G_2$
be the subgraphs induced by these two components, with
$|G_1|\ge |G_2|$
. It then follows that
$|G_1|\ge n$
and
$\kappa (G_1)\ge 2$
.
Since
$\kappa (G_1)\ge 2$
, by Lemma 2.1 and Claims 1 and 2, the circumference of
$G_1$
satisfies
$$ \begin{align*}c(G_1)\ge \min\{2\delta(G_1), |G_1|\}\ge \min\{2(\delta(G')-1), |G_1|\}\ge n.\end{align*} $$
If
$G_1$
is bipartite, then
$\alpha (G_1)\ge (|G'|-1)/4\ge 2m+2$
. Thus,
$\overline {G_1}$
contains
$K_{2m+2}$
as a subgraph, which implies that
$\overline {G_1}$
contains
$W_{2m+1}$
as a subgraph, which is a contradiction. Hence,
$G_1$
is not bipartite.
Since
$|G_2|\ge \delta (G'-u_1)+1\ge \delta (G')$
, we have
$$ \begin{align*}|G_1|=|G'|-1-|G_2|\le |G'|-\delta(G')-1.\end{align*} $$
From Claim 2, it follows that
$\delta (G')-1\ge (|G'|-\delta (G')+1)/3$
and, thus,
$\delta (G_1)\ge \delta (G')-1\ge (|G_1|+2)/3$
. By Lemma 2.5,
$G_1$
is weakly pancyclic and has girth
$3$
or
$4$
.
Combining the weak pancyclicity of
$G_1$
with
$c(G_1)\ge n$
, we conclude that
$G_1$
contains
$C_n$
as a subgraph, leading to a contradiction. This completes the proof.
Claim 6. There exist two vertices
$u_1$
and
$u_2$
in
$G'$
such that
$G'-\{u_1,u_2\}$
has exactly three connected components.
Proof. We proceed by contradiction. Suppose not. Then, by Claim 5, there exist two vertices
$u_1$
and
$u_2$
in
$G'$
such that
$G'-\{u_1,u_2\}$
has at least four connected components. Each connected component has order at least
$$ \begin{align*}\delta(G'-\{u_1,u_2\})+1\ge \delta(G')-1\ge m.\end{align*} $$
Therefore, the complement of
$G'-\{u_1,u_2\}$
contains the complete 4-partite graph
$K_{m,m,m,m}$
as a subgraph and, thus, contains
$W_{2m+1}$
as a subgraph. This contradicts the assumption that
$\overline {G'}$
does not contain
$W_{2m+1}$
as a subgraph.
Let
$U_1$
,
$U_2$
and
$U_3$
denote the three connected components of
$G'-\{u_1,u_2\}$
. We now state the next claim.
Claim 7. For each
$j\in [3]$
, the subgraph
$G[U_j]$
is a complete graph and
$$ \begin{align*} n/2+m\le |U_j|\le n-1. \end{align*} $$
Proof. For each
$j\in [3]$
, we have
$$ \begin{align*} |U_j|\ge \delta(G[U_j])+1\ge \delta(G')-1\ge |G'|-2n\ge n-(2m+1)t+2m-1\ge n/2+m. \end{align*} $$
The last three inequalities follow from Claims 2, 1 and the lower bound on n.
Suppose, in contrast, that
$G[U_1]$
is not a complete graph. Then, there exist vertices
$u,v\in U_1$
such that
$uv\in E(\overline {G}[U_1])$
. Let
$U_2'\subseteq U_2$
and
$U_3'\subseteq U_3$
be arbitrary subsets of size m. Then, the induced subgraph
$\overline {G}[\{u,v\}\cup U_2'\cup U_3']$
contains a copy of
$W_{2m+1}$
centred at either u or v, which yields a contradiction. Therefore,
$G[U_1]$
must be a complete graph. By the same argument,
$G[U_2]$
and
$G[U_3]$
are also complete graphs.
Finally, we show that
$|U_j|\le n-1$
. Suppose otherwise that
$|U_j|\ge n$
. Since
$G[U_j]$
is a complete graph, it must contain a cycle
$C_n$
as a subgraph, which contradicts our assumption. Hence,
$|U_j|\le n-1$
.
Claim 8. For each
$i\in [2]$
, there exists some
$j\in [3]$
such that the vertex
$u_i$
has at least
$|U_j|-m+1$
neighbours in
$U_j$
.
Proof. Suppose the claim is false. The vertex
$u_i$
has at least m nonneighbours in each of
$U_1$
,
$U_2$
and
$U_3$
. Select m such nonneighbours from each of
$U_1$
,
$U_2$
and
$U_3$
. Together with
$u_i$
, these vertices induce a copy of the complete 4-partite graph
$K_{1,m,m,m}$
in
$\overline {G'}$
, and it contains
$W_{2m+1}$
as a subgraph. This contradiction completes the proof.
Recall that the graph
$\overline {G}-V(G')$
contains x vertex-disjoint copies of
$W_{2m+1}$
. For each such copy of
$W_{2m+1}$
, we have the following claim.
Claim 9. In each
$W_{2m+1}$
, except for at most one vertex, every other vertex has at least
$|U_j|-2m+1$
neighbours in some
$U_j$
with
$j \in [3]$
.
Proof. We proceed by contradiction. Suppose that in some
$W_{2m+1}$
, say F, there exist two vertices
$v_1$
and
$v_2$
such that for every
$j\in [3]$
, each of them has at most
$|U_1|-2m$
neighbours in
$U_j$
.
Under this assumption, we can choose m nonneighbours of
$v_1$
in
$U_1$
(denoted by
$X_1$
) and m nonneighbours of
$v_2$
in
$U_1$
(denoted by
$Y_1$
) such that
$X_1\cap Y_1=\emptyset $
. Similarly, choose m nonneighbours of
$v_1$
in
$U_2$
(denoted by
$X_2$
) and m nonneighbours of
$v_2$
in
$U_2$
(denoted by
$Y_2$
) with
$X_2\cap Y_2=\emptyset $
. Likewise, choose m nonneighbours of
$v_1$
in
$U_3$
(denoted by
$X_3$
) and m nonneighbours of
$v_2$
in
$U_3$
(denoted by
$Y_3$
) with
$X_3\cap Y_3=\emptyset $
.
Since
$U_1$
,
$U_2$
and
$U_3$
are the three connected components of
$G'-\{v_1,v_2\}$
, the subgraph
$\overline {G}[U_1,U_2,U_3]$
forms a complete tripartite graph. Consequently, in
$\overline {G}$
, the induced subgraph
$\overline {G}[\{v_1\}\cup X_1\cup X_2\cup X_3]$
contains a copy of
$W_{2m+1}$
centred at
$v_1$
, and
$\overline {G}[\{v_2\}\cup Y_1\cup Y_2\cup Y_3]$
contains a copy of
$W_{2m+1}$
centred at
$v_2$
.
By removing F from the original x vertex-disjoint copies of
$W_{2m+1}$
and adding the two newly constructed ones, we obtain
$x+1$
vertex-disjoint copies of
$W_{2m+1}$
in
$\overline {G}$
, which contradicts the maximality of x. This completes the proof of the claim.
Next, we classify the vertices outside
$\bigcup _{j=1}^3U_j$
as follows: if a vertex has at least
${|U_j|-2m+1}$
neighbours in
$U_j$
, then we assign it to
$V_j$
for
$j\in [3]$
. According to Claims 8 and 9, there are at most x vertices not contained in
$\bigcup _{j=1}^3(U_j\cup V_j)$
. In other words, the number of vertices in
$\bigcup _{j=1}^3(U_j\cup V_j)$
is at least
$3n+t-3-x\ge 3n-2$
. By the pigeonhole principle, there exists some
$j\in [3]$
such that
$|U_j\cup V_j|\ge n$
. Without loss of generality, assume that
$|U_1\cup V_1|\ge n$
. We then select
$n-|U_1|$
vertices from
$V_1$
and still denote this subset by
$V_1$
.
Let
$H:=G[U_1\cup V_1]$
be the induced subgraph and denote its closure by
$\text {cl}(H)$
. We now show that
$\text {cl}(H)$
is the complete graph
$K_n$
. By Claims 7, 8 and 9, for every pair of nonadjacent vertices
$\{u,v\}$
in H, where
$u\in U_1$
and
$v\in V_1$
,
$$ \begin{align*} d_H(u)+d_H(v)\ge (|U_1|-1)+(|U_1|-2m+1)=2|U_1|-2m\ge n. \end{align*} $$
Hence, when constructing
$\text {cl}(H)$
, we add edges
$uv$
to H such that each vertex in
$V_1$
eventually becomes adjacent to all vertices in
$U_1$
. Therefore, every vertex in
$V_1$
has degree at least
$|U_1|$
in
$\text {cl}(H)$
. Furthermore, for every pair of nonadjacent vertices
$\{u',v'\}$
in
$V_1$
, we have
$d_{\text {cl}(H)}(u')+d_{\text {cl}(H)}(v')\ge 2|U_1|\ge n$
, so we continue adding the edge
$u'v'$
. Following this procedure, the resulting graph
$\text {cl}(H)$
becomes a complete graph of order n.
Since complete graphs are Hamiltonian,
$\text {cl}(H)$
is Hamiltonian. By Lemma 2.4, H is also Hamiltonian and thus contains a
$C_n$
as a subgraph, which is a final contradiction.
