# The number of cliques in graphs covered by long cycles

Naidan Ji and Dong Ye School of Mathematics and Statistics, Ningxia
University, Yinchuan, Ningxia 750021. Email<EMAIL_ADDRESS>of
Mathematical Sciences and Center for Computational Science, Middle Tennessee
State University, Murfreesboro, TN 37132. Email<EMAIL_ADDRESS>Partially
supported by Simons Foundation award no. 359516.

###### Abstract

Let $G$ be a 2-connected $n$-vertex graph and $N_{s}(G)$ be the total number
of $s$-cliques in $G$. Let $k\geq 4$ and $s\geq 2$ be integers. In this paper,
we show that if $G$ has an edge $e$ which is not on any cycle of length at
least $k$, then $N_{s}(G)\leq r{k-1\choose s}+{t+2\choose s}$, where
$n-2=r(k-3)+t$ and $0\leq t\leq k-4$. This result settles a conjecture of Ma
and Yuan and provides a clique version of a theorem of Fan, Wang and Lv. As a
direct corollary, if $N_{s}(G)>r{k-1\choose s}+{t+2\choose s}$, every edge of
$G$ is covered by a cycle of length at least $k$.

Keywords: clique, long cycle, the Erdős-Gallai theorem

##  1 Introduction

All graphs considered in this paper are simple. Let $G$ be a graph and and
$N_{s}(G)$ be the total number of $s$-cliques in $G$ (a complete subgraph with
$s$ vertices). Particularly, $N_{2}(G)$ is the number of edges of $G$, which
is often denoted by $e(G)$. The well-known Erdős-Gallai theorem [1] states
that if a graph with $n$ vertices has no cycle of length at least $k$ where
$n\geq k\geq 3$, then $e(G)\leq(k-1)(n-1)/2$, which was originally conjectured
by Turán (cf. [6]). The Erdős-Gallai theorem was improved by Kopylov [9] for
2-connected graphs.

Before presenting Kopylov’s result, we need some extra notations. Let
$H_{n,k,a}$ be an $n$-vertex graph whose vertex set can be partitioned into
three sets $A$, $B$ and $C$ such that $|A|=a$, $|B|=n-(k-a)$ and $|C|=k-2a$,
where integers $n,k$ and $a$ satisfy $n\geq k\geq 4$ and $k/2>a\geq 1$, and
whose edge set consists of all edges between $A$ and $B$, and all edges in
$A\cup C$. Note that $H_{n,k,a}$ is 2-connected if $a\geq 2$ and has no cycle
longer than $k-1$. For $s\geq 2$, define

$f_{s}(n,k,a)={k-a\choose s}+(n-k+a){a\choose s-1}.$

Then $N_{s}(H_{n,k,a})=f_{s}(n,k,a)$ and, particularly,
$e(H_{n,k,a})=N_{2}(H_{n,k,a})=f_{2}(n,k,a)$. The following is Kopylov’s
result for 2-connected graphs.

######  Theorem 1.1 (Kopylov, [9]).

Let $G$ be a 2-connected graph on $n$ vertices, and let $n\geq k\geq 5$ and
$t=\lfloor\frac{k-1}{2}\rfloor$. If $G$ has no cycle of length at least $k$,
then

$e(G)\leq\max\\{f_{2}(n,k,2),f_{2}(n,k,t)\\},$

and the equality holds only if $G=H_{n,k,2}$ or $G=H_{n,k,t}$.

It is worth mentioning that Fan, Lv and Wang [4] proved a result slightly
stronger than the above theorem for $n\geq k\geq 2n/3$. Together with a result
of a result of Woodall [13], it provided an alternative proof of Theorem 1.1.
Recently, a clique version of Theorem 1.1 has been proven by Luo [10] as
follows.

######  Theorem 1.2 (Luo, [10]).

Let $G$ be a 2-connected $n$-vertex graph, and let $n\geq k\geq 5$ and
$t=\lfloor\frac{k-1}{2}\rfloor$. If $G$ has circumference less than $k$, then
the number of $s$-cliques of $G$ satisfies

$N_{s}(G)\leq\max\\{f_{s}(n,k,2),f_{s}(n,k,t)\\}.$

A stability result of the Theorem 1.2 is obtained Ma and Yuan [11], which also
can be viewed as the clique version of a stability result of Theorem 1.1 given
by Füredi, Kostochka and Verstraëte [5].

Another result of Erdős and Gallai in [1] shows that a graph without a path of
length at least $k$ has $e(G)\leq n(k-2)/2$. The result of Erdős and Gallai
for paths was strengthened by Fan for 2-connected graphs (Theorem 5 in [2]),
which states that the longest path between any pair of vertices in a
2-connected graph with more than $(k+2)(n-2)/2$ edges has length at least $k$.
Fan’s result is sharp when $n-2$ is divisible by $k-2$, which was further
sharpened by Wang and Lv [12] for all possible values $n\geq 3$. The sharpness
of the results of Fan [2], Wang and Lv [12] can be shown by the following
constructions.

Let $X_{n,k}$ to be an $n$-vertex graph defined as follows. Assuming
$n-2=r(k-3)+t$ where $0\leq t\leq k-4$, the graph $X_{n,k}$ consists of three
disjoint parts $A$, $B$ and $C$ such that $A$ is an edge $uv$, and $B$ is a
union of $r$ vertex disjoint $(k-3)$-cliques, and $C$ is a $t$-clique, and all
edges between $A$ and $B\cup C$. For $s\geq 2$, define

$g_{s}(n,k)=\left\\{\begin{aligned} &r{k-1\choose s}+{t+2\choose s}&\mbox{ if
}s\geq 3;\\\ &r{k-3\choose 2}+{t\choose 2}+2(n-2)+1&\mbox{ if
}s=2.\end{aligned}\right.$

Then $g_{s}(n,k)=N_{s}(X_{n,k})$, and
$e(X_{n,k})=N_{2}(X_{n,k})=g_{2}(n,k)\leq r{k-1\choose 2}+{t+2\choose 2}$.
These graphs $X_{n,k}$ have no cycle containing the edge $uv$ longer than
$k-1$. Note that, if $k>n$, then $X_{n,k}$ is a clique and
$g_{s}(n,k)={n\choose s}$.

######  Theorem 1.3 (Fan [2], Wang and Lv [12] ).

Let $G$ be a 2-connected $n$-vertex graph with $n\geq 3$. If $G$ has an edge
$uv$ such that $G$ has no cycle of length at least $k\geq 4$ containing $uv$.
Then

$e(G)\leq g_{2}(n,k).$

In [11], Ma and Yuan made the following conjecture, which can be treated as a
clique version of Theorem 1.3. As indicated in [11], the conjecture (if it is
true) is a key tool to prove a more general stability result of of Theorem
1.2.

######  Conjecture 1.4 (Ma and Yuan, [11]).

Let $G$ be a 2-connected $n$-vertex graph with $n\geq 3$ and let $uv$ be an
edge in $G$. Let $k\geq 4$ and $s\geq 2$ be integers, and let $n-2=r(k-3)+t$
for some $0\leq t\leq k-4$. If

$N_{s}(G)>r{k-1\choose s}+{t+2\choose s},$

then there is a cycle on at least $k$ vertices containing the edge $uv$.

Note that, the bound of the above conjecture is not the best possible for the
case $s=2$ because of Theorem 1.3 and $g_{2}(n,k)<r{k-1\choose 2}+{t+2\choose
2}$ for $n\geq k$. The following is our main result, which completely settles
Conjecture 1.4.

######  Theorem 1.5.

Let $G$ be a 2-connected $n$-vertex graph with $n\geq 3$. If $G$ has an edge
$uv$ such that $G$ has no cycle containing $uv$ of length at least $k\geq 4$,
then the number of $s$-cliques of $G$ with $s\geq 2$ satisfies

$N_{s}(G)\leq g_{s}(n,k).$

The bound in Theorem 1.5 is sharp due to these graphs $X_{n,k}$ constructed
above. A direct corollary of Theorem 1.5 shows that if the clique number of a
graph $G$ is large enough, every edge of $G$ belongs to a long cycle.

######  Corollary 1.6.

Let $G$ be a 2-connected $n$-vertex graph with $n\geq 3$. If
$N_{s}(G)>g_{s}(n,k)$ where $k\geq 4$ and $s\geq 2$, then every edge of $G$ is
covered by a cycle of length at least $k$.

##  2 Preliminaries

Let $X_{n,k}$ be an $n$-vertex graph defined in the previous section, and let
$Q_{n,k}$ be the $n$-vertex graph with $n\geq 2$ obtained from $X_{n+1,k+1}$
by contracting the edge $uv$ of $A$ into a single vertex $w$. Then for graphs
$Q_{n,k}$, it holds that $n-1=r(k-2)+t$ and $0\leq t\leq k-3$. For $s\geq 2$,
define

$\psi_{s}(n,k)=r{k-1\choose s}+{t+1\choose s}.$

Then $\psi_{s}(n,k)=N_{s}(Q_{n,k})$. Note that, if $k>n$, then $Q_{n,k}$ is a
clique and $\psi_{s}(n,k)={n\choose s}$. Let $f_{s}(n,k,a)$ the function
defined in the previous section. By comparing the graphs $H_{n,k,2}$,
$H_{n,k,\lfloor\frac{k-1}{2}\rfloor}$ and the graph $Q_{n,k}$, it not hard to
derive the following proposition.

######  Proposition 2.1.

For integers $n\geq k\geq 5$ and $s\geq 2$, the functions $f_{s}(n,k,a)$ and
$\psi_{s}(n,k)$ satisfy

$\max\\{f_{s}(n,k,2),f_{s}(n,k,\lfloor\frac{k-1}{2}\rfloor)\\}\leq\psi_{s}(n,k).$

The following result slightly strengthens Luo’s clique version of the Erdős-
Gallai theorem (Corollary 1.5 in [10]), which serves as an important step
toward the proof of our main result—Theorem 1.5. Note that, the bound in this
result is sharp because of the graphs $Q_{n,k}$ constructed above.

######  Theorem 2.2.

Let $G$ be a connected $n$-vertex graph with $n\geq 2$. If $G$ has no cycle of
length at least $k\geq 4$, then the number of $s$-cliques with $s\geq 2$ of
$G$ satisfies

$N_{s}(G)\leq\psi_{s}(n,k).$

###### Proof.

Let $G$ be a connected $n$-vertex graph with $n\geq 2$. Use induction on $n$,
the number of vertices of $G$. The result holds trivially for $n\leq 3$. So
assume that $n\geq 4$ in the following, and the theorem holds for all
connected graphs with the number of vertices smaller than $n$.

If $k=4$, every maximal 2-connected subgraph of $G$ is a triangle because the
longest cycle of $G$ has length at most $k-1=3$. So each block of $G$ is
either a triangle or a single edge. It follows that $N_{3}(G)\leq(n-1)/2$ and
equality holds if and only if $G$ is the graph with $(n-1)/2$ triangles
sharing a common vertex, and $N_{2}(G)\leq\psi_{2}(n,k)$. Hence

$N_{s}(G)\leq\psi_{s}(n,k),$

and the theorem holds. So, in the following, assume that $k\geq 5$.

First, assume that $G$ is 2-connected. If $n<k$, then

$N_{s}(G)\leq{n\choose s}=\psi_{s}(n,k)$

and hence the theorem holds. If $n\geq k\geq 5$, then it follows from Theorem
1.2 and Proposition 2.1 that

$N_{s}(G)\leq\max\\{f_{s}(n,k,2),f_{s}(n,k,\lfloor\frac{k-1}{2}\rfloor)\\}\leq\psi_{s}(n,k),$

and the theorem holds.

Hence, we may assume that $G$ has a cut-vertex $v$. Let $H$ be a connected
component of $G-v$, and let $G_{1}=G[H\cup\\{v\\}]$ and $G_{2}=G-H$. Then both
$G_{1}$ and $G_{2}$ are connected and $G_{1}\cap G_{2}=\\{v\\}$. For each
$i\in[2]$, let $n_{i}=|V(G_{i})|\geq 2$, and assume $n_{i}-1=r_{i}(k-2)+t_{i}$
with $0\leq t_{i}\leq k-3$. Then $n=n_{1}+n_{2}-1$. Then, for $s\geq 2$, the
following inequality holds,

${t_{1}+1\choose s}+{t_{2}+1\choose s}\leq\left\\{\begin{aligned}
&{t_{1}+t_{2}+1\choose s}\mbox{\hskip 85.35826pt if }t_{1}+t_{2}\leq k-2;\\\
&{k-1\choose s}+{t_{1}+t_{2}-k+3\choose s}\mbox{\hskip 17.07182pt if }k-1\leq
t_{1}+t_{2}\leq 2(k-3).\end{aligned}\right.$ (1)

Applying inductive hypothesis to each $G_{i}$, we have

$\displaystyle N_{s}(G)$
$\displaystyle=N_{s}(G_{1})+N_{s}(G_{2})\leq\psi_{s}(n_{1},k)+\psi_{s}(n_{2},k)$
$\displaystyle=r_{1}{k-1\choose s}+{t_{1}+1\choose s}+r_{2}{k-1\choose
s}+{t_{2}+1\choose s}$ $\displaystyle\leq\psi_{s}(n,k),$

where the last inequality follows from Inequality (1). This completes the
proof. ∎

Another ingredient we need to prove Theorem 1.5 is edge-switching operation,
which was introduced by Fan [3] to study subgraph covering. This operation
appears in an earlier paper [8] of Klemans which studied the probabilities of
the number of connected components under this operation.

Let $G$ be a graph and $v$ be a vertex of $G$. Let $N(v)=\\{u|uv\in E(G)\\}$
and let $N[v]=N(v)\cup\\{v\\}$. The degree of $v$ in $G$ is denoted by
$d_{G}(v)$ which is equal to $|N(v)|$. For a given edge $uv$, an edge-
switching from $v$ to $u$ is to replace each edge $vx$ by a new edge $ux$ for
every $x\in N(v)\backslash N[u]$. The resulting graph is called the edge-
switching graph of $G$ from $v$ to $u$, denoted by $G[v\to u]$. The following
lemma is a trivial observation.

######  Lemma 2.3.

Let $G$ be a 2-connected graph and let $uv$ be an edge of $G$.
(i) If $N(u)\cap N(v)=\emptyset$ and $G/uv$ is not 2-connected, then
$\\{u,v\\}$ is a vertex cut of $G$.
(ii) If $N(u)\cap N(v)\neq\emptyset$ and the edge-switching graph $G[v\to u]$
is not 2-connected, then $\\{u,v\\}$ is a vertex cut of $G$.

The following lemma shows that the edge-switching operation does not increase
the length of longest cycles through certain edges.

######  Lemma 2.4 (Ji and Chen, [7]).

Let $G$ be a connected graph and let $uv$ be an edge. For any edge $ux$, let
$k$ be the length of a longest cycle of $G$ containing $ux$. Then the length
of a longest cycle containing $ux$ in the edge-switching graph $G[v\to u]$ is
at most $k$.

The contraction and the edge-switching operations do not reduce the number of
$s$-cliques except small values of $s$ as shown in the following lemma.

######  Lemma 2.5.

Let $G$ be a connected graph and let $uv$ be an edge of $G$.
(i) If $N(u)\cap N(v)=\emptyset$ and $s\geq 3$, then $N_{s}(G/uv)\geq
N_{s}(G)$;
(ii) For $s\geq 2$, it holds that $N_{s}(G[v\to u])\geq N_{s}(G)$.

###### Proof.

(i) Since $N(u)\cap N(v)=\emptyset$, the graph $G$ has no $s$-cliques
containing $uv$ for $s\geq 3$. Hence, every $s$-clique of $G$ remains as an
$s$-clique in $G/uv$. Hence (1) follows.

(ii) Let $S(G)$ be the set of unlabeled copies of $K_{s}$ in a graph $G$.
Consider an edge-switching from $v$ to $u$, and let $G^{\prime}=G[v\to u]$.
Denote $W=\\{vx|x\in N(v)\backslash N[u]\\}$. Define a map $\pi:S(G)\to
S(G^{\prime})$ as follows, for each $Q\in S(G)$,

$\pi(Q)=\begin{cases}Q&\text{if $E(Q)\cap W=\emptyset$,}\\\
Q^{\prime}&\text{otherwise,}\end{cases}$

where $V(Q^{\prime})=(V(Q)\backslash\\{v\\})\cup\\{u\\}$ and
$E(Q^{\prime})=(E(Q)\backslash W)\cup\\{ux\,|\,vx\in W\cap E(Q)\\}$. If $vx\in
W\cap E(Q)$, then $x\in N(v)\backslash N[u]$ and it follows that $u\notin Q$.
All neighbors of $v$ in $Q$ are neighbors of $u$ in $Q^{\prime}$. Hence
$Q^{\prime}$ is indeed an $s$-clique of $G^{\prime}$. So $\pi$ is well-
defined. Note that, $\pi(Q_{1})\neq\pi(Q_{2})$ for two different $s$-cliques
$Q_{1}$ and $Q_{2}$ of $G$. Therefore $\pi$ is an injection. So $N_{s}(G[v\to
u])\geq N_{s}(G)$ and (ii) holds. ∎

##  3 Proof of Theorem 1.5

Now, we are ready to prove our main theorem. Note that Theorem 1.5 follows
from Theorem 1.3 directly for the case $s=2$. In the following, we only need
to prove it for $s\geq 3$.

Proof of Theorem 1.5. Suppose to the contrary that $G$ is a counterexample.
For an edge $e$ of $G$, let $c_{e}(G)$ be the maximum length of cycles
containing $e$. Then $G$ is a 2-connected $n$-vertex graph with
$N_{s}(G)>g_{s}(n,k)$ but does have an edge $e$ such that $c_{e}(G)<k$. Let

$\ell(G)=\max\\{d_{G}(v)|v\mbox{ is an end-vertex of some edge }e\mbox{ with
}c_{e}(G)<k\\}.$

Among all the counterexamples, choose $G$ such that: (1) the number of
vertices of $G$ is as small as possible, and (2) subject to (1), $\ell(G)$ is
as large as possible.

Note that the theorem holds trivially for $n=3$. If $k=4$, then $G$ consists
of $n-2$ triangles which share a common edge. Then $N_{3}(G)=n-2=g_{3}(n,4)$
and $N_{s}(G)=0$ for $s\geq 4$, a contradiction to that $G$ is a
counterexample. So in the following, assume that $n\geq 4$ and $k\geq 5$.

Claim 1. The graph $G$ does not have a 2-vertex cut $\\{x,y\\}$ such that $xy$
is an edge.

Proof of Claim 1. If not, assume that $\\{x,y\\}$ is a vertex cut of $G$ with
$xy\in E(G)$. Let $H_{1}$ a connected component of $G-\\{x,y\\}$. Further, let
$G_{1}=G[V(H_{1})\cup\\{x,y\\}]$ and $G_{2}=G-H_{1}$. Then both $G_{1}$ and
$G_{2}$ are 2-connected. For convenience, let $|V(G_{i})|=n_{i}\geq 3$, and
$n_{i}-2=r_{i}(k-3)+t_{i}$ and $0\leq t_{i}\leq k-4$ for $i\in[2]$.

If $N_{s}(G_{i})>g_{s}(n_{i},k)$ for some $i\in[2]$, without loss of
generality assume $N_{s}(G_{1})>g_{s}(n_{1},k)$. Since $G$ is a counterexample
with the smallest number of vertices, the subgraph $G_{1}$ is smaller and
hence not a counterexample. Therefore, $c_{e}(G_{1})\geq k$ for any edge $e\in
E(G_{1})$. So $c_{e}(G)\geq c_{e}(G_{1})\geq k$ for each $e\in E(G_{1})$. For
an edge $e^{\prime}\in E(G_{2})$ and $e^{\prime}\neq xy$, it follows from
2-connectivity of $G_{2}$ that $G_{2}$ has a cycle $C^{\prime}$ containing
both $e^{\prime}$ and $xy$. Let $C$ be a longest cycle of $G_{1}$ containing
$xy$. Then $(C\cup C^{\prime})-\\{xy\\}$ is a cycle of $G$ which contains
$e^{\prime}$ and

$c_{e^{\prime}}(G)\geq|V(C)|+|V(C^{\prime})|-2>|V(C)|\geq c_{xy}(G_{1})\geq
k.$

Thus, $c_{e}(G)\geq k$ for any edge $e\in E(G)$, a contradiction to that $G$
has an edge $e$ with $c_{e}(G)<k$. Hence $N_{s}(G_{i})\leq g_{s}(n_{i},k)$
holds for both $i=1$ and $i=2$. Therefore,

$\displaystyle N_{s}(G)$ $\displaystyle=N_{s}(G_{1})+N_{s}(G_{2})\leq
g_{s}(n_{1},k)+g_{s}(n_{2},k)$ (2) $\displaystyle=r_{1}{k-1\choose
s}+{t_{1}+2\choose s}+r_{2}{k-1\choose s}+{t_{2}+2\choose s}$
$\displaystyle=(r_{1}+r_{2}){k-1\choose s}+{t_{1}+2\choose s}+{t_{2}+2\choose
s}.$

For $s\geq 3$, the following inequality holds,

${t_{1}+2\choose s}+{t_{2}+2\choose s}\leq\left\\{\begin{aligned}
&{t_{1}+t_{2}+2\choose s}\mbox{\hskip 85.35826pt if }t_{1}+t_{2}\leq k-4;\\\
&{k-1\choose s}+{t_{1}+t_{2}-k+5\choose s}\mbox{\hskip 17.07182pt if }k-3\leq
t_{1}+t_{2}\leq 2(k-4).\end{aligned}\right.$ (3)

Note that, $n=n_{1}+n_{2}-2$ and hence $n-2=(r_{1}+r_{2})(k-3)+(t_{1}+t_{2})$,
which implies $r=r_{1}+r_{2}$ and $t=t_{1}+t_{2}$ if $t_{1}+t_{2}\leq k-4$,
and $r=r_{1}+r_{2}+1$ and $t=t_{1}+t_{2}-k+3$ if $k-3\leq t_{1}+t_{2}\leq
2(k-4)$. Combining Inequalities (2) and (3), it follows that

$N_{s}(G)\leq g_{s}(n,k).$

This yields a contradiction to that $N_{s}(G)>g_{s}(n,k)$, which completes the
proof of Claim 1.

Choose an edge $uv$ of $G$ such that $c_{uv}(G)<k$ and $d_{G}(v)\leq
d_{G}(u)=\ell(G)$. Then the vertex $u$ satisfies the following claim.

Claim 2. The vertex $u$ is adjacent to all vertices of $G-u$.

Proof of Claim 2. Suppose to the contrary that there exists a vertex $w$ in
$G$ such that $uw\notin E(G)$. Since $G$ is 2-connected, there is a
$(u,w)$-path $P$ which does not contain $v$. Choose $P=uu_{1}\cdots u_{k}w$ to
be a shortest $(u,w)$-path avoiding $v$. Then $uu_{i}\notin E(G)$ for $i\geq
2$. If $N(u)\cap N(u_{1})=\emptyset$, then contract the edge $uu_{1}$ and let
$G^{\prime}=G/uu_{1}$. By (i) of Lemma 2.3 and Claim 1, the graph $G^{\prime}$
is 2-connected. Since $uu_{1}\neq uv$, it follows that

$c_{uv}(G^{\prime})\leq c_{uv}(G)<k.$

Since $G^{\prime}$ is smaller than $G$, the graph $G^{\prime}$ is not a
counterexample and hence $N_{s}(G^{\prime})\leq g_{s}(n-1,k)$. It follows from
(i) of Lemma 2.5 that

$N_{s}(G)\leq N_{s}(G^{\prime})\leq g_{s}(n-1,k)\leq g_{s}(n,k),$

which contradicts the assumption $N_{s}(G)>g_{s}(n,k)$.

So assume that $N(u)\cap N(u_{1})\neq\emptyset$. Let
$G^{\prime\prime}=G[u_{1}\to u]$. Then $d_{G^{\prime\prime}}(u)>d_{G}(u)$
because $u_{2}$ and $w$ are not adjacent to $u$. By (ii) of Lemma 2.3 and
Claim 1, the graph $G^{\prime\prime}$ is 2-connected. It follows from Lemma
2.4 that $c_{uv}(G^{\prime\prime})\leq c_{uv}(G)<k$. Further, by (ii) of Lemma
2.5, it holds that

$N_{s}(G^{\prime\prime})\geq N_{s}(G)>g_{s}(n,k).$

Then $\ell(G^{\prime\prime})\geq d_{G^{\prime\prime}}(u)>d_{G}(u)=\ell(G)$
because $uu_{2}\notin E(G)$, which contradicts the maximality of $\ell(G)$.
This completes the proof of Claim 2.

By Claim 2, $u$ is adjacent to all other vertices of $G$. Further, we have the
following claim.

Claim 3. The graph $G-u$ has no cycle of length at least $k-1$.

Proof of Claim 3. Suppose to the contrary that $G-u$ has a cycle
$C=x_{1}x_{2}\ldots x_{l}x_{1}$ with $l\geq k-1$. If $v\in V(C)$, let
$v=x_{1}$ (relabelling $x_{i}$’s if necessary). Then $uvx_{2}\ldots x_{l}u$ is
a cycle of length at least $k$ containing $uv$ in $G$ because $u$ is adjacent
to all other vertices of $G$, a contradiction to $c_{uv}(G)<k$. Now assume
$v\notin V(C)$. Since $G$ is 2-connected, the graph $G-u$ is connected. Hence
$G-u$ has a path from $v$ to $C$ which is internally disjoint from $C$.
Without loss of generality, assume $x_{1}$ is the end-vertex of $P$ on $C$.
Then $uvPx_{1}x_{2}\ldots x_{l}u$ is a cycle of $G$ which has length at least
$k$, a contradiction to $c_{uv}(G)<k$. This completes the proof of Claim 3.

By Claim 3 and Theorem 2.2, we have

$N_{s}(G-u)\leq\psi_{s}(n-1,k-1)=r{k-2\choose s}+{t+1\choose s},$

where $(n-1)-1=r(k-3)+t$ and $0\leq t\leq k-4$. By Claim 2, it follows that

$\displaystyle N_{s}(G)$ $\displaystyle=N_{s}(G-u)+N_{s-1}(G-u)$
$\displaystyle\leq r{k-2\choose s}+{t+1\choose s}+r{k-2\choose
s-1}+{t+1\choose s-1}$ $\displaystyle=r{k-1\choose s}+{t+2\choose s}$
$\displaystyle=g_{s}(n,k),$

which yields a desired contradiction to $N_{s}(G)>g_{s}(n,k)$. This completes
the proof. ∎

## References

  * [1] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar. 10 (3) (1959) 337–356.
  * [2] G. Fan, Long cycles and the codiameter of a graph I, J. Combin. Theory Ser. B 49 (1990) 151–180.
  * [3] G. Fan, Subgraph coverings and edge switchings, J. Combin. Theory Ser. B 84 (2002) 54–83.
  * [4] G. Fan, X. Lv and P. Wang, Cycles in 2-connected graphs, J. Combin. Theory Ser. B 92 (2004) 379–394.
  * [5] Z. Füredi, A. Kostochka and J. Verstraëte, Stability in the Erdős-Gallai Theorem on cycles and paths, J. Combin. Theory Ser. B 121 (2016) 197–228.
  * [6] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, Bolyai Math. Studies 25, pp. 169–264, Erdős Centennial (L. Lovász, I. Ruzsa, and V. T. Sós, Eds.) Springer, 2013.
  * [7] N. Ji and M. Chen, Graphs with almost all edges in long cycles, Graphs Combin. 34 (2018) 1295–1314.
  * [8] A.K. Kelmans, On graphs with randomly deleted edges, Acta Math. Acda. Sci. Hungar. 37 (1981) 77–88.
  * [9] G. N. Kopylov, On maximal paths and cycles in a graph, Soviet Math. Dokl. 18 (1977) 593–596.
  * [10] R. Luo, The maximum number of cliques in graphs without long cycles, J. Combin. Theory Ser. B  128 (2018) 219–226.
  * [11] J. Ma and L.-T. Yuan, A clique version of the Erdős-Gallai stability theorem, (2020), arXiv: 2010.13667v2.
  * [12] P. Wang and X. Lv, The codiameter of 2-connected graphs, Discrete Math. 308 (2008) 113–122.
  * [13] D. R. Woodall, Maximal circuits of graphs I, Acta Math. Hungar. 28 (1976), 77–80.