Graphs with Almost All Edges in Long Cycles

Abstract

For an edge e of a given graph G, define $c_e(G)$ be the length of a longest cycle of G containing e. Wang and Lv (2008) gave a tight function $f_{0}(n,k)$ (for integers $n\ge 3$ and $k\ge 4$), such that for any 2-connected graph G on n vertices with more than $f_{0}(n,k)$ edges, every edge belongs to a cycle of length at least k, i.e., $c_e(G)\ge k$ for every edge $e\in E(G)$. In this work we give a tight function f(n, k) (for integers $n\ge k\ge 6$), such that for any 2-connected graph G on n vertices with more than f(n, k) edges, we have that $c_e(G)\ge k$ for all but at most one edge of G.

1 Introduction

The graphs considered here are finite, undirected and simple (no loops or parallel edges). The sets of vertices and edges of a graph G are denoted by V(G) and E(G), respectively. The order of a graph G is the number of its vertices. Define $e(G)=|E(G)|$. The union of two graphs $G_{1}$ and $G_{2}$, denoted by $G_{1}\cup G_{2}$, is the graph with vertex set $V(G_{1})\cup V(G_{2})$ and edge set $E(G_{1})\cup E(G_{2})$. The union of m disjoint copies of the same graph G is denoted by mG. The join of two disjoint graphs $G_{1}$ and $G_{2}$, denoted by $G_{1}\vee G_{2}$, is obtained from their union by joining each vertex of $G_{1}$ to each vertex of $G_{2}$.

A classical result of Erdös and Gallai [2] is that for an integer $k\ge 2$, if G is a graph on n vertices with more than $\frac{k}{2}(n-1)$ edges, then G contains a cycle of length more than k. The result is best possible when $n-1$ is divisible by $k-1$, in view of the graph consisting of copies of $K_{k}$ all having exactly one vertex in common. Woodall [6] improved the result by giving best possible bounds for the remaining cases when $n-1$ is not divisible by $k-1$. Caccetta and Vijayan [1] gave an alternative proof of the same result, and in addition, characterized the structure of the extremal graphs. For 2-connected graphs, Woodall [6] obtained the bound for the case when $2\le k\le \frac{2n+2}{3}$, and Fan et al. [4] completed all the rest cases when $\frac{2}{3}n+1\le k\le n-1$ by using an edge-switching technique.

Let $c_{e}(G)$ be the length of a longest cycle which contains e in G. In [5], Wang and Lv gave the maximum number of edges a 2-connected graph can have with at least one edge e of G such that $c_{e}(G)\le k-1$, as the following theorem states. For integers $n\ge 3$ and $k\ge 4$, define $f_{0}(n,k)=q\left( {\begin{array}{c}k-3\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n-2)+1$, where $n-2=q(k-3)+r$, $0\le r< k-3$.

Theorem 1.1

[5] For integers $n\ge 3$ and $k\ge 4$, let G be a 2-connected graph on n vertices. If there exists an edge uv of G such that $c_{uv}(G)\le k-1$, then

$$\begin{aligned} e(G)\le f_{0}(n,k), \end{aligned}$$

with equality if and only if (i) $G\cong uv\vee (qK_{k-3}\cup K_{r})$; or (ii) $G\cong (uv\vee q'K_{k-3})\cup (uv\vee K_{t-2}\vee \overline{K}_{n'-t})$, with $k=2t$ and $r=\frac{k-2}{2}$ or $\frac{k-4}{2}$, where $t\ge 3$, $0\le q'< q$ and $n'=n-q'(k-3)$.

Let $F_{G}=\{e|e\in G\ \mathrm{and}\ c_{e}(G)\le k-1\}$. In Theorem 1.1, it means that if $e(G)>f_{0}(n,k)$, then $c_{e}(G)\ge k$ for every $e\in E(G)$, i.e., $|F_{G}|=0$. As a generalization of Theorem 1.1, we give a tight function f(n, k), such that for any 2-connected graph G on n vertices with $e(G)>f(n,k)$, then $c_{e}(G)\ge k$ for all but at most one edge of G, i.e., $|F_{G}|\le 1$.

For integers $n\ge k\ge 6$, define $f_{1}(n,k)= q_{1}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n-2)+1$, where $n-3=q_{1}(k-4)+r_{1}, q_{1}\ge 0,0\le r_{1}<k-4$; $f_{2}(n,k)=\left( {\begin{array}{c}\frac{k}{2}\\ 2\end{array}}\right) +\frac{k}{2}\left( n-\frac{k}{2}\right)$, if k is even, otherwise $f_{2}(n,k)=\left( {\begin{array}{c}\frac{k-1}{2}\\ 2\end{array}}\right) +\frac{k-1}{2}\left( n-\frac{k-1}{2}\right) +1$; $f_{3}(n,k)=\left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3(n-k+2).$ We get the following result.

Theorem 1.2

For integers $n\ge k\ge 6$, let G be a 2-connected graph on n vertices. If

$$\begin{aligned} e(G)>f(n,k), \end{aligned}$$

then $|F_{G}|\le 1$, where $f(n,k)=\mathrm{max}\{f_{1}(n,k),f_{2}(n,k),f_{3}(n,k)\}$.

We shall show that the function f(n, k) is tight. For integers $n\ge k\ge 6$, let

$$\begin{aligned} G_{1}= & {} K_{2}\vee (K_{1}\cup q_{1}K_{k-4}\cup K_{r_{1}}), \hbox {where } n-3=q_{1}(k-4)+r_{1}, q_{1}\ge 0 \quad \hbox { and }\quad 0\le r_{1}< k-4,\\ G_{2}= & {} \left\{ \begin{array}{ll}K_{\frac{k}{2}}\vee \left( n-\frac{k}{2}\right) K_{1}, &{} \quad \text{ if } k \text{ is } \text{ even, }\\ K_{\frac{k-1}{2}}\vee \left( K_{2}\cup \left( n-\frac{k+3}{2}\right) K_{1}\right) , &{}\quad \text{ otherwise, }\end{array}\right. \\ G_{3}= & {} K_{3}\vee \left( K_{k-5}\cup \left( n-k+2\right) K_{1}\right) . \end{aligned}$$

It’s easy to see that $|F_{G_{i}}|\ge 2$ and $e(G_{i})=f_{i}(n,k)$ for $i=1,2,3$. In this sense, Theorem 1.2 is best possible.

Let H be a subgraph of G, $N_{H}(x)$ is the set of the neighbors of x which are in H, and $d_{H}(x)=|N_{H}(x)|$. When no confusion can occur, we shall write N(x) and d(x), instead of $N_{G}(x)$ and $d_{G}(x)$. For subgraphs F and H, E(F, H) denotes the set, and e(F, H) the number, of edges with one end in F and the other end in H. For simplicity, we write E(F) and e(F) for E(F, F) and e(F, F), respectively. In particular, $e(G)=|E(G)|$. Note $G-H$ denotes the graph obtained from G by deleting all vertices of H together with all the edges with at least one end in H. For $E'\subseteq E(G)$, $G-E'$ denotes the graph obtained from G by deleting all the edges of $E'$. Let $S\subseteq V(G)$. A subgraph H is induced by S if $V(H)=S$ and $xy\in E(H)$ if and only if $xy\in E(G)$, we denote H by G[S]. We say S is an independent set if $E(S)=\emptyset$. Let $P=a_{1}a_{2}\ldots a_{n}$ be a path. We can assume that P has an orientation which is consistent with the increasing order of the indices of $a_{i}$, $1\le i\le n$. For $a\in V(P)$, define $a^{-}$ and $a^{+}$ to be the vertices on P immediately before and after a, respectively, according to the orientation of P. Similar definition can be given for an oriented cycle C.

2 Some Lemmas

The concept of edge-switching is given by Fan in [3]. Let uv be an edge in a graph G and let $Z=N(v)\backslash (N(u)\cup \{u\})$. An edge-switching from v to u is to delete $\{vz|z\in Z\}$ and add $\{uz|z\in Z\}$. The resulting graph, denoted by $G[v\rightarrow u]$, is called an edge-$switching\ graph$ of G (from v to u). Let $H=\{uz|z\in Z\}$. Then we have the following lemma.

Lemma 2.1

If G is a connected graph and uv is an edge of G, let $G'=G[v\rightarrow u]$, then the following statements are true.

• (a) For any edge $e=ux,\ x\in N_{G}(u)$, we have that $c_{e}(G')\le c_{e}(G)$.

• (b) For any edge $e=vy,\ y\in N_{G}(v)\backslash \{u\}$, we have that $c_{uy}(G')\le c_{vy}(G)$.

• (c) For any edge e which isn’t incident with u and v in G, we have that $c_{e}(G')\le c_{e}(G)$.

Proof

(a) Suppose, to the contrary, that there is an edge $e=ux,\ x\in N_{G}(u)$, such that $c_{e}(G')>c_{e}(G)$. That is, there is a cycle $C'$ in $G'$, which contains e and with $e(C')> c_{e}(G)$. In the following, we shall always find a cycle C in G, such that $e\in C$ and $e(C)\ge e(C')>c_{e}(G)$. That’s a contradiction which completes the proof.

If $E(C')\cap H=\emptyset$, then we can choose $C=C'$. Thus, we can assume that $E(C')\cap H\ne \emptyset$. Since $|E(C')\cap H|\le 1$, we can assume that $|E(C')\cap H|=1$. Let $E(C')\cap H=\{uy\}$.

If $x=v$, then without loss of generality, we can assume that $C'=uvz\ldots yu$, where $uy\in H$ and $z\in N_{G}(u)\cap N_{G}(v)$. (See Fig. 1a). Then let $C=(C'\backslash \{uy,vz\})\cup \{uz,vy\}$.

Fig. 1

The cases of $C'=uvz\dots yu$ and $C'=ux\dots yu$

If $x\ne v$, then there are two subcases. If $v\notin C'$, then we can assume that $C'=ux\ldots yu$, where $uy\in H$. (See Fig. 1b). Then let $C=(C'\backslash \{uy\})\cup \{uv,vy\}$. If $v\in C'$, then we can assume that $C'=ux\ldots z_{1}vz_{2}\ldots yu$, where $uy\in H$ and $\{z_{1},z_{2}\}\subseteq N_{G}(u)\cap N_{G}(v)$. (See Fig. 2). Then let $C=(C'\backslash \{uy,vz_{2}\})\cup \{uz_{2},vy\}$.

Fig. 2

The case of $C'=ux\dots z_{1}vz_{2}\dots yu$

(b) Note that for any $y\in N_{G}(v)\backslash \{u\}$, whenever $uy\in H$ or not, the discussions in the following are the same. Similar with the proof of (a), suppose, to the contrary, that for some $y\in N_{G}(v)\backslash \{u\}$, $c_{uy}(G')>c_{vy}(G)$. Assume that $C'$ is a cycle in $G'$ such that $uy\in C'$ and $e(C')=c_{uy}(G')$. We shall find a cycle C in G, such that $e=vy\in C$ and $e(C)\ge e(C')>c_{vy}(G)$. This produces a contradiction.

If $v\notin C'$, then we assume that $C'=uy\ldots xu$. If $ux\notin H$, then let $C=(C'\backslash \{uy\})\cup \{uv,vy\}$. If $ux\in H$, then let $C=(C'\backslash \{ux,uy\})\cup \{vx,vy\}$.

If $v\in C'$, then there are two subcases. If $uv\in E(C')$, then without loss of generality, we can assume that $C'=uy\ldots zvu$. Then let $C=(C'\backslash \{uy,vz\})\cup \{uz,vy\}$. If $uv\notin E(C')$, then we assume that $C'=uy\ldots z_{1}vz_{2}\ldots wu$. If $uw\notin H$, then let $C=(C'\backslash \{uy,vz_{1}\})\cup \{uz_{1},vy\}$. If $uw\in H$, then let $C=(C'\backslash \{uw,uy,vz_{1},vz_{2}\})\cup \{uz_{1},uz_{2},vw,vy\}$.

(c) The proof is similar with the above discussion. We shall omit the details here. $\square$

The following lemma is easy to prove, so we omit the details here. Let $e=xy$ be an edge of G. By G / e we denote the graph obtained from G by contracting the edge e into a new vertex w which becomes adjacent to all the former neighbors of x and of y.

Lemma 2.2

Let G be a 2-connected graph and let uv be an edge of G.

• (i) If G isn’t isomorphic to $K_{3}$ and G / uv isn’t 2-connected, then $\{u,v\}$ is a vertex cut of G.

• (ii) If $N(u)\cap N(v)\ne \emptyset$, and the edge-switching graph $G[v\rightarrow u]$ isn’t 2-connected, then $\{u,v\}$ is a vertex cut of G.

Lemma 2.3

For integers $n\ge 0$ and $m>0$, define $l(n,m)=q\left( {\begin{array}{c}m\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right)$, where $n=qm+r$, $q\ge 0$ and $0\le r<m$. Then

$$\begin{aligned} l(n,m+1)\ge l(n,m). \end{aligned}$$

Proof

Let $l(n,m+1)=q'\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right)$, where $n=q'(m+1)+r'$, $q'\ge 0$ and $0\le r'<m+1$. Clearly $q'\le q$.

If $q'=q$, then $r'=r-q$. Thus

$$\begin{aligned} l(n,m+1)-l(n,m)= & {} \frac{1}{2}[q'm(m+1)+r'(r'-1)-qm(m-1)-r(r-1)]\quad \qquad \\= & {} \frac{1}{2}[q^{2}+q(2m-2r+1)].\nonumber \end{aligned}$$

(2.1)

Since $r<m$, $l(n,m+1)\ge l(n,m)$.

If $q'=q-1$, then $r'=m-(q-1-r)$. Using $q'=q-1$ in (2.1),

$$\begin{aligned} l(n,m+1)-l(n,m)=\frac{1}{2}[2qm-m(m+1)+r'(r'-1)-r(r-1)]. \end{aligned}$$

(2.2)

Using $m+1=r'-r+q$ in (2.2),

$$\begin{aligned} l(n,m+1)-l(n,m)= & {} \frac{1}{2}[2qm-m(r'-r+q)+r'(r'-1)-r(r-1)]\nonumber \\= & {} \frac{1}{2}[qm-r'(m-r'+1)+r(m-r+1)]. \end{aligned}$$

(2.3)

Since $m-r'+1=q-r\le q$ and $r'\le m$, $r'(m-r'+1)\le qm$. Note that $r<m$. By (2.3), $l(n,m+1)-l(n,m)\ge 0$. That is, $l(n,m+1)\ge l(n,m)$.

If $q'\le q-2$, note that $q=\frac{n-r}{m}$ and $q'=\frac{n-r'}{m+1}$, then we obtain $\frac{n-r'}{m+1}\le \frac{n-r}{m}-2$. That is, $n\ge m(m+1)+r(m+1)+m(m+1-r')\ge m(m+1)$. Using $qm=n-r$ and $q'(m+1)=n-r'$ in (2.1),

$$\begin{aligned} l(n,m+1)-l(n,m)= & {} \frac{1}{2}[(n-r')m+r'(r'-1)-(n-r)(m-1)-r(r-1)]\nonumber \\= & {} \frac{1}{2}[n-r'm+r'(r'-1)+r(m-r)]. \end{aligned}$$

(2.4)

Since $r'<m+1$, $r'm<(m+1)m\le n$. Note that $r<m$. By (2.4), $l(n,m+1)-l(n,m)\ge 0$. That is, $l(n,m+1)\ge l(n,m)$.

Consequently, in each case we have that $l(n,m+1)\ge l(n,m)$. This completes the proof of Lemma 2.3. $\square$

By Lemma 2.3, we can easily get the following result.

Corollary 2.4

For integers $n\ge 0$ and $m>0$, define $l(n,m)=q\left( {\begin{array}{c}m\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right)$, where $n=qm+r$, $q\ge 0$ and $0\le r<m$. Then $l(n,m_{1})\ge l(n,m_{2})$, for integers $m_{1}\ge m_{2}>0$.

Lemma 2.5

For integers $0\le r_{1}\le r_{2}<k$, let $r_{1}+r_{2}=qk+r$, where $q\ge 0$ and $0\le r<k$, then we have that

$$\begin{aligned} \left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) \le q\left( {\begin{array}{c}k\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) , \end{aligned}$$

the equality holds if and only if $r_{1}=0$ or $r_{2}=0$.

Proof

Since $0\le r_{1}\le r_{2}<k$, we have that $0\le r_{1}+r_{2}<2k$, which implies that $0\le q\le 1$.

If $q=0$, then $r=r_{1}+r_{2}$. So

$$\begin{aligned} \left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) = \left( {\begin{array}{c}r_{1}+r_{2}\\ 2\end{array}}\right) -r_{1}r_{2}\le \left( {\begin{array}{c}r\\ 2\end{array}}\right) , \end{aligned}$$

the equality holds if and only if $r_{1}=0$ or $r_{2}=0$.

If $q=1$, then $r_{1}+r_{2}=k+r$. Let $l=r_{1}+r_{2}=k+r$. Note that $r_{1}\le r_{2}$ and $r<k$. So $r_{1}\le \frac{l}{2}$ and $r<\frac{l}{2}$. Since $r_{2}<k$, we have that $r_{1}>r$.

$$\begin{aligned} \left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) -\left( {\begin{array}{c}k\\ 2\end{array}}\right) -\left( {\begin{array}{c}r\\ 2\end{array}}\right)= & {} \left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}l-r_{1}\\ 2\end{array}}\right) -\left( {\begin{array}{c}l-r\\ 2\end{array}}\right) -\left( {\begin{array}{c}r\\ 2\end{array}}\right) \nonumber \\= & {} r(l-r)-r_{1}(l-r_{1}). \end{aligned}$$

(2.5)

Let $f(x)=x(l-x)$. Since $0\le r<r_{1}\le \frac{l}{2}$ and f(x) is a strictly increasing function on the interval $[0,\frac{l}{2}]$, $f(r)<f(r_{1})$. That is, $r(l-r)<r_{1}(l-r_{1})$. By (2.5), $\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) <\left( {\begin{array}{c}k\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right)$.

In each case, we have that $\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) \le q\left( {\begin{array}{c}k\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right)$, and the equality holds if and only if $r_{1}=0$ or $r_{2}=0$. $\square$

Lemma 2.6

For integers $n\ge k\ge 6$, define

$$\begin{aligned} f(n,k)=\mathrm{max}\{f_{1}(n,k),f_{2}(n,k),f_{3}(n,k)\}, \end{aligned}$$

where $f_{i}(n,k)$ $(1\le i\le 3)$ is defined as in Theorem 1.2. For integers $n\ge 2$ and $k\ge 6$, define

$$\begin{aligned} g(n,k)=q'\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) +2(n-2)+1, \end{aligned}$$

where $n-2=q'(k-5)+r'$, $q'\ge 0$ and $0\le r'<k-5$. Then we have that

$$\begin{aligned} f(n_{1},k)+g(n_{2},k)-1\le f(n,k), \end{aligned}$$

where $n_{1},n_{2}$ are integers, $n\ge n_{1}\ge k\ge 6$ and $n=n_{1}+n_{2}-2$.

Proof

Let

$$\begin{aligned}&f_{1}(n_{1},k)=q_{1}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)+1,\\&g(n_{2},k)=q_{2}\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1,\\&f_{1}(n,k)=q\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n-2)+1, \end{aligned}$$

where

$$\begin{aligned} n_{1}-3= & {} q_{1}(k-4)+r_{1}, q_{1}\ge 0 \quad \hbox { and }\quad 0\le r_{1}<k-4;\\ n_{2}-2= & {} q_{2}(k-5)+r_{2}, q_{2}\ge 0 \quad \hbox { and }\quad 0\le r_{2}<k-5;\\ n-3= & {} q(k-4)+r, q\ge 0 \hbox { and } 0\le r<k-4. \end{aligned}$$

Claim 1

$f_{1}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n,k)$.

Define $h(n_{2},k)=q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) +2(n_{2}-2)+1$, where $n_{2}-2=q_{3}(k-4)+r_{3}$, $q_{3}\ge 0$ and $0\le r_{3}<k-4.$ By Lemma 2.3, $q_{2}\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) \le q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right)$. Thus

$$\begin{aligned} g(n_{2},k)\le h(n_{2},k). \end{aligned}$$

(2.6)

Since $n_{1}-3=q_{1}(k-4)+r_{1}$, $n_{2}-2=q_{3}(k-4)+r_{3}$ and $n=n_{1}+n_{2}-2$, we have that $n-3=(q_{1}+q_{3})(k-4)+(r_{1}+r_{3})$. Note that $0\le r_{1}<k-4$ and $0\le r_{3}<k-4$. Let $r_{1}+r_{3}=q'(k-4)+r'$, where $q'\ge 0$ and $0\le r'<k-4.$ Hence, by Lemma 2.5,

$$\begin{aligned} \left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) \le q'\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) . \end{aligned}$$

(2.7)

And $n-3=(q_{1}+q_{3})(k-4)+q'(k-4)+r'=(q_{1}+q_{3}+q')(k-4)+r'$, $0\le r'<k-4.$ Since $n-3=q(k-4)+r$, $q\ge 0$ and $0\le r<k-4$, it follows that $q=q_{1}+q_{3}+q'$ and $r=r'$.

$$\begin{aligned} f_{1}(n_{1},k)+h(n_{2},k)-1= & {} q_{1}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)\nonumber \\&+1+q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) +2(n_{2}-2)+1-1\nonumber \\= & {} (q_{1}+q_{3})\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) +2(n_{1}+n_{2}-4)+1. \end{aligned}$$

(2.8)

Using $n=n_{1}+n_{2}-2$ and (2.7) in (2.8),

$$\begin{aligned} f_{1}(n_{1},k)+h(n_{2},k)-1\le & {} (q_{1}+q_{3})\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +q'\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) +2(n-2)+1\\= & {} q\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n-2)+1\\= & {} f_{1}(n,k). \end{aligned}$$

Then by (2.6), we have that $f_{1}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n_{1},k)+h(n_{2},k)-1\le f_{1}(n,k)$.

Claim 2

$f_{2}(n_{1},k)+g(n_{2},k)-1\le f_{2}(n,k)$.

If k is even, then $f_{2}(n,k)=\left( {\begin{array}{c}\frac{k}{2}\\ 2\end{array}}\right) +\frac{k}{2}(n-\frac{k}{2})$. Note that $q_{2}(k-5)=n_{2}-2-r_{2}$.

$$\begin{aligned}&f_{2}(n_{1},k)+g(n_{2},k)-1\nonumber \\&\quad =\left( {\begin{array}{c}\frac{k}{2}\\ 2\end{array}}\right) +\frac{k}{2}\left( n_{1}-\frac{k}{2}\right) +\frac{q_{2}(k-5)(k-6)}{2}+\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1-1\nonumber \\&\quad =\left( {\begin{array}{c}\frac{k}{2}\\ 2\end{array}}\right) +\frac{k}{2}\left( n_{1}-\frac{k}{2}\right) +\frac{(n_{2}-2-r_{2})(k-6)}{2}+\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)\nonumber \\&\quad =\left( {\begin{array}{c}\frac{k}{2}\\ 2\end{array}}\right) +\frac{k}{2}\left( n_{1}+n_{2}-2-\frac{k}{2}\right) +\frac{1}{2}r_{2}[r_{2}-(k-5)]+(2-n_{2}). \end{aligned}$$

(2.9)

Using $n=n_{1}+n_{2}-2$ in (2.9),

$$\begin{aligned} f_{2}(n_{1},k)+g(n_{2},k)-1= f_{2}(n,k)+\frac{1}{2}r_{2}[r_{2}-(k-5)]+(2-n_{2}). \end{aligned}$$

(2.10)

Note that $r_{2}<k-5$ and $n_{2}\ge 2$. By (2.10), $f_{2}(n_{1},k)+g(n_{2},k)-1\le f_{2}(n,k)$.

If k is odd, then $f_{2}(n,k)=\left( {\begin{array}{c}\frac{k-1}{2}\\ 2\end{array}}\right) +\frac{k-1}{2}(n-\frac{k-1}{2})+1$. Note that $q_{2}(k-5)=n_{2}-2-r_{2}$ and $n=n_{1}+n_{2}-2$.

$$\begin{aligned}&f_{2}(n_{1},k)+g(n_{2},k)-1\\&\quad =\left( {\begin{array}{c}\frac{k-1}{2}\\ 2\end{array}}\right) +\frac{k-1}{2}\left( n_{1}-\frac{k-1}{2}\right) +1+\frac{q_{2}(k-5)(k-6)}{2}+\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) \\&\qquad +2(n_{2}-2)+1-1\\&\quad =\left( {\begin{array}{c}\frac{k-1}{2}\\ 2\end{array}}\right) +\frac{k-1}{2}\left( n_{1}-\frac{k-1}{2}\right) +1+\frac{(n_{2}-2-r_{2})(k-6)}{2}+\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) \\&\qquad +2(n_{2}-2) \\&\quad =f_{2}(n,k)+\frac{1}{2}[(2-n_{2})+r_{2}(r_{2}-(k-5))]. \end{aligned}$$

Since $n_{2}\ge 2$ and $r_{2}<k-5$, it follows that $f_{2}(n_{1},k)+g(n_{2},k)-1\le f_{2}(n,k)$.

Claim 3

$f_{3}(n_{1},k)+g(n_{2},k)-1\le f(n,k)$.

If $k=6,7$, then $f_{3}(n_{1},k)=f_{2}(n_{1},k)$. If $k=8$, since $n_{1}\ge k\ge 8$, then $f_{3}(n_{1},k)\le f_{2}(n_{1},k)$. That is, $f_{3}(n_{1},k)\le f_{2}(n_{1},k)$ for $6\le k\le 8$. By Claim 2, $f_{3}(n_{1},k)+g(n_{2},k)-1\le f_{2}(n_{1},k)+g(n_{2},k)-1\le f_{2}(n,k)\le f(n,k)$. Therefore, the result is true for $6\le k\le 8$.

If $n_{2}\le 5$, then

$$\begin{aligned} g(n_{2},k)= & {} q_{2}\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1\\\le & {} \left( {\begin{array}{c}q_{2}(k-5)+r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1\\= & {} \left( {\begin{array}{c}n_{2}-2\\ 2\end{array}}\right) +2(n_{2}-2)+1 \\= & {} \frac{(n_{2}-2)(n_{2}-3)}{2}+2(n_{2}-2)+1\\\le & {} 3(n_{2}-2)+1. \end{aligned}$$

Hence,

$$\begin{aligned} f_{3}(n_{1},k)+g(n_{2},k)-1\le & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3(n_{1}-k+2)+3(n_{2}-2)+1-1\\= & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3(n-k+2)\\= & {} f_{3}(n,k)\\\le & {} f(n,k). \end{aligned}$$

Thus we may suppose that $k\ge 9$ and $n_{2}\ge 6$. In the following, we shall compare $f_{3}(n_{1},k)$ with $f_{1}(n_{1},k)$ and use Claim 1 which has been proved to obtain our result. Note that $f_{1}(n_{1},k)=q_{1}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)+1$, where $n_{1}-3=q_{1}(k-4)+r_{1}$. Since $n_{1}\ge k$, we have that $q_{1}\ge 1$. We distinguish two cases according to $q_{1}$ and $r_{1}$.

Case 1  $q_{1}\ge 2$ or $r_{1}\ge 4$.

$$\begin{aligned} f_{1}(n_{1},k)= & {} q_{1}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)+1 \\= & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +(q_{1}-1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-k+2)\\= & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +[(q_{1}-1)(k-4)+r_{1}+1]+2(n_{1}-k+2) \\&+ \frac{(q_{1}-1)(k-4)(k-7)}{2}+\frac{r_{1}(r_{1}-3)}{2}-1 \\= & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3(n_{1}-k+2)+\frac{(q_{1}-1)(k-4)(k-7)}{2}+\frac{r_{1}(r_{1}-3)}{2}-1\\= & {} f_{3}(n_{1},k)+\frac{(q_{1}-1)(k-4)(k-7)}{2}+\frac{r_{1}(r_{1}-3)}{2}-1. \end{aligned}$$

Note that $k\ge 9$ and $r_{1}\ge 0$. Clearly, if $q_{1}\ge 2$ or $r_{1}\ge 4$, then $\frac{(q_{1}-1)(k-4)(k-7)}{2}+\frac{r_{1}(r_{1}-3)}{2}-1\ge 0$. That is, $f_{1}(n_{1},k)\ge f_{3}(n_{1},k)$. By Claim 1, $f_{3}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n,k)\le f(n,k)$.

Case 2  $q_{1}=1$ and $r_{1}\le 3$.

Since $n_{1}-3=(k-4)+r_{1}$, we have that $r_{1}=n_{1}-k+1\ge 1$.

$$\begin{aligned} f_{1}(n_{1},k)= & {} \left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)+1 \nonumber \\= & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3(n_{1}-k+2)+\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) -(n_{1}-k+1+1) \nonumber \\= & {} f_{3}(n_{1},k)+\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) -(r_{1}+1)\nonumber \\= & {} f_{3}(n_{1},k)+\frac{r_{1}(r_{1}-3)}{2}-1. \end{aligned}$$

(2.11)

Since $1\le r_{1}\le 3$, $\frac{r_{1}(r_{1}-3)}{2}\ge -1$. By (2.11), $f_{1}(n_{1},k)\ge f_{3}(n_{1},k)-2$. That is,

$$\begin{aligned} f_{3}(n_{1},k)\le f_{1}(n_{1},k)+2. \end{aligned}$$

(2.12)

In the following, we shall prove that

$$\begin{aligned} f_{1}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n,k)-2. \end{aligned}$$

(2.13)

$$\begin{aligned}&f_{1}(n_{1},k)+g(n_{2},k)-1\nonumber \\&\quad =\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)+1\nonumber \\&\qquad +q_{2}\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1-1. \end{aligned}$$

(2.14)

If $q_{2}\ge 1$, then $q_{2}-1\ge 0$. Note that $r_{1}\ge 1$. By (2.14), we have that

$$\begin{aligned}&f_{1}(n_{1},k)+g(n_{2},k)-1\nonumber \\&\quad =\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left[ \left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) \right] \nonumber \\&\qquad +2(n_{1}-2)+(q_{2}-1)\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1 \nonumber \\&\quad =\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left[ \left( {\begin{array}{c}r_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) -(k-4-r_{1})\right] \nonumber \\&\qquad +2(n_{1}-2)+(q_{2}-1)\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) \nonumber \\&\qquad +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1. \end{aligned}$$

(2.15)

Let $n_{1}'=n_{1}+(k-5)$ and $n_{2}'=n_{2}-(k-5)$. Clearly, $n_{1}'\ge n_{1}\ge k$ and $n=n_{1}'+n_{2}'-2$. Then

$$\begin{aligned} f_{1}(n_{1}',k)= & {} 2\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}-1\\ 2\end{array}}\right) +2(n_{1}'-2)+1,\\ g(n_{2}',k)= & {} (q_{2}-1)\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}'-2)+1. \end{aligned}$$

Since $k\ge 9$ and $1\le r_{1}\le 3$, we have that $k-4-r_{1}\ge 2$. By (2.15),

$$\begin{aligned} f_{1}(n_{1},k)+g(n_{2},k)-1\le & {} 2\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}-1\\ 2\end{array}}\right) -2+2(n_{1}+(k-5)-2) \nonumber \\&+(q_{2}-1)\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-(k-5)-2)+1 \nonumber \\= & {} f_{1}(n_{1}',k)+g(n_{2}',k)-3. \end{aligned}$$

(2.16)

By Claim 1, $f_{1}(n_{1}',k)+g(n_{2}',k)-1\le f_{1}(n,k)$. Using this in (2.16), we have that $f_{1}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n,k)-2$.

If $q_{2}=0$, then $r_{2}\ge 4$ since $n_{2}\ge 6$. Note that $n_{1}-3=(k-4)+r_{1}$ and $n_{2}-2=r_{2}$, where $0\le r_{1}<k-4$ and $0\le r_{2}<k-5$.

$$\begin{aligned}&f_{1}(n_{1},k)+g(n_{2},k)-1\nonumber \\&\quad =\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) +2(n_{1}-2)+1+\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n_{2}-2)+1-1 \nonumber \\&\quad =\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left[ \left( {\begin{array}{c}r_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}+1\\ 2\end{array}}\right) -(r_{2}-r_{1}+1)\right] +2(n-2)+1. \end{aligned}$$

(2.17)

Note that $r_{1}-1<k-4$ and $r_{2}+1<k-4$. Let $(r_{1}-1)+(r_{2}+1)=q'(k-4)+r'$, where $q'\ge 0$ and $0\le r'<k-4$. Then by Lemma 2.5,

$$\begin{aligned} \left( {\begin{array}{c}r_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}+1\\ 2\end{array}}\right) \le q'\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) . \end{aligned}$$

(2.18)

Since $r_{1}\le 3$ and $r_{2}\ge 4$, we have that $r_{2}-r_{1}+1\ge 2$. Using (2.18) in (2.17), we obtain

$$\begin{aligned} f_{1}(n_{1},k)+g(n_{2},k)-1\le & {} \left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +q'\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) -2+2(n-2)+1 \nonumber \\= & {} (q'+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) +2(n-2)+1-2. \end{aligned}$$

(2.19)

Note that $n-3=n_{1}+n_{2}-5=(k-4)+r_{1}+r_{2}=(q'+1)(k-4)+r'=q(k-4)+r$, where $q'+1\ge 0$ and $0\le r'<k-4$. Hence, $f_{1}(n,k)=(q'+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) +2(n-2)+1$. By (2.19), we have that

$$\begin{aligned} f_{1}(n_{1},k)+g(n_{2},k)-1\le f_{1}(n,k)-2. \end{aligned}$$

This completes the proof of (2.13).

Combining (2.12) with (2.13), we obtain

$$\begin{aligned} f_{3}(n_{1},k)+g(n_{2},k)-1\le & {} f_{1}(n_{1},k)+2+g(n_{2},k)-1\\\le & {} f_{1}(n,k)-2+2=f_{1}(n,k)\le f(n,k). \end{aligned}$$

In either case, we have that $f_{3}(n_{1},k)+g(n_{2},k)-1\le f(n,k)$, and we complete the proof of Claim 3.

By Claims 1, 2 and 3, we can easily obtain that

$$\begin{aligned} f(n_{1},k)+g(n_{2},k)-1\le f(n,k). \end{aligned}$$

This ends the proof of the lemma. $\square$

3 Proof of Theorem 1.2

The proof needs the following theorems. The first one is a result of Fan et al. [4]. Define $t(n,k)=\mathrm{max}\{\left( {\begin{array}{c}k-1\\ 2\end{array}}\right) +2(n-k+1),\left( {\begin{array}{c}k+1-\lfloor \frac{k}{2}\rfloor \\ 2\end{array}}\right) +\lfloor \frac{k}{2}\rfloor (n-k-1+\lfloor \frac{k}{2}\rfloor )\}.$

Theorem 3.1

[4] For integers $3\le k\le n$, let G be a 2-connected graph on n vertices. If the length of a longest cycle of G is not more than k, then $e(G)\le t(n,k)$.

For 2-connected graph G, let $c_{(e,e')}(G)$ be the length of a longest cycle containing both e and $e'$ in G.

Theorem 3.2

Let G be a 2-connected graph of order $n\ge 5$.

• (i) If $e(G)>\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$, then any two edges of G lie on a common cycle of length n.

• (ii) If $e(G)\ge \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$, then any two edges of G lie on a common cycle of length more than $n-2$.

Proof

We begin with a claim.

Claim. If $e(G)\ge \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$, then for any two edges $e_{1}$ and $e_{2}$ of G, there is a Hamilton path P of G containing both $e_{1}$ and $e_{2}$, and one endvertex of P is neither incident with $e_{1}$ nor incident with $e_{2}$ in P.

If $e(G)\ge \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$, then by Theorem 1.1, $c_{e}(G)=n$ for any edge e of G. Let $C=u_{1}u_{2}\ldots u_{n}$ be a Hamilton cycle containing $e_{1}$. If $e_{2}\in C$, note that $n\ge 5$, then there exists an edge $e'\in C$ $(e'\ne e_{1},e_{2})$ such that one end of $e'$ isn’t incident with $e_{1}$ and $e_{2}$. Then $P=C-e'$ is a Hamilton path with the required properties. If $e_{2}\notin C$, then without loss of generality, we can assume that $e_{1}=u_{i}u_{i+1}$ and $e_{2}=u_{j}u_{k}$, where $1\le i<j<k-1\le n-1$. Clearly, we can choose $P=u_{j+1}\overrightarrow{C}u_{k}u_{j}\overleftarrow{C}u_{k+1}$ (note that $u_{n+1}=u_{1}$). It ends the proof of the claim.

Now we shall prove (i) and (ii) respectively.

(i) Suppose to the contrary that there are two edges $e_{1}$ and $e_{2}$ with $c_{(e_{1},e_{2})}(G)<n$. Since $e(G)>\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$, by the claim, there is a Hamilton path $P=u_{1}u_{2}\ldots u_{n}$ containing $e_{1}$ and $e_{2}$, and without loss of generality, we may assume that $e_{1}=u_{k}u_{k+1}$ and $e_{2}=u_{l}u_{l+1}$, where $2\le k<l\le n-1$. Clearly, $u_{1}u_{n}\notin G$.

If $u_{n}u_{i}\in G$, where $2\le i\le n-1$, $i\ne k, l$, then $u_{1}u_{i+1}\notin G$, for otherwise, $C=u_{1}u_{i+1}\overrightarrow{P}u_{n}u_{i}\overleftarrow{P}u_{1}$ is a Hamilton cycle of G containing $e_{1}$ and $e_{2}$, a contradiction. Hence, for each vertex $u_{i}$ of $N(u_{n})\backslash \{u_{k},u_{l}\}$, there is a vertex $u_{i+1}$ of $V(G)\backslash \{u_{1}\}$ not adjacent to $u_{1}$. Thus, $d(u_{1})\le (n-1)-(d(u_{n})-2)$, that is, $d(u_{1})+d(u_{n})\le n+1$. Note that $u_{1}u_{n}\notin G$. Then

$$\begin{aligned} e(G)=d(u_{1})+d(u_{n})+e(G-\{u_{1},u_{n}\})\le n+1+\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) =\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3. \end{aligned}$$

This contradiction completes the proof of (i).

(ii) Suppose to the contrary that there are two edges $e_{1}$ and $e_{2}$ such that $c_{(e_{1},e_{2})}(G)\le n-2$. Since $e(G)\ge \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$, by similar discussion as above, we have that there is a Hamilton path $P=u_{1}u_{2}\ldots u_{n}$ containing $e_{1}$ and $e_{2}$, where $e_{1}=u_{k}u_{k+1}$ and $e_{2}=u_{l}u_{l+1}$ ($2\le k<l\le n-1$), and $d(u_{1})+d(u_{n})\le n+1$. Clearly, $u_{1}u_{n}\notin G$ and $u_{2}u_{n}\notin G$ since $c_{(e_{1},e_{2})}(G)\le n-2$.

Note that $e(G)=e(G-u_{n})+d(u_{n})$ and $e(G)\ge \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3$. We have that $d(u_{n})\ge 3$. If $d(u_{n})=3$, then $G-u_{n}\cong K_{n-1}$. In this case, it’s easy to see that any two edges lie on a common cycle of length more than $n-2$, a contradiction. Hence, we may assume that $d(u_{n})\ge 4$.

If $u_{n}u_{i}\in G$, where $3\le i\le n-1$, $i\ne k,l$, then $u_{2}u_{i+1}\notin G$, for otherwise, $C=u_{2}u_{i+1}\overrightarrow{P}u_{n}u_{i}\overleftarrow{P}u_{2}$ is a cycle containing $e_{1}$ and $e_{2}$ of order $n-1$, a contradiction. Hence, $N(u_{2})\cap (N^{+}(u_{n}){\setminus }\{u_{k+1},u_{l+1}\})=\emptyset$. Since $d(u_{n})\ge 4$, $|N^{+}(u_{n}){\setminus }\{u_{k+1},u_{l+1}\}|\ge 2$. So

$$\begin{aligned} d(u_{2})\le |V(G){\setminus }\{u_{2}\}|-|N^{+}(u_{n}){\setminus }\{u_{k+1},u_{l+1}\}|\le (n-1)-2=n-3. \end{aligned}$$

Thus,

$$\begin{aligned} e(G)= & {} e(G-\{u_{1},u_{2},u_{n}\})+d(u_{1})+d(u_{2})+d(u_{n})-e(G[\{u_{1},u_{2},u_{n}\}])\\\le & {} \left( {\begin{array}{c}n-3\\ 2\end{array}}\right) +(n+1)+(n-3)-1\\< & {} \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) +3. \end{aligned}$$

This contradiction completes the proof of (ii), and of the theorem. $\square$

The following theorem is a special case of Theorem 1.2 when $k=n$. We state it here in order to make the proof of Theorem 1.2 not too lengthy.

Theorem 3.3

Let G be a 2-connected graph of order $n\ge 6$. Let $F^{*}=\{e|e\in G$ and $\ c_{e}(G)\le n-1\}$. If $|F^{*}|\ge 2$, then $e(G)\le f(n,n)$, where f(n, n) is defined as in Theorem 1.2.

Proof

Without loss of generality, we can suppose that G is edge maximal with respect to the condition that $|F^{*}|\ge 2$. Then for any two nonadjacent vertices u and v of G, we have that $c_{e'}(G+uv)=n$ for some $e'\in F^{*}$. It means that there is a uv-path $P:\ u=u_{1}u_{2}\ldots u_{n}=v$ containing $e'$, say $e'=u_{k}u_{k+1}$ ($1\le k\le n-1$) in G. Since $c_{e'}(G)\le n-1$, we get that $N(u)\cap (N^{+}(v)\backslash \{u_{k+1}\})=\emptyset$. Thus, $d(u)\le (n-1)-(d(v)-1)$. That is, $d(u)+d(v)\le n$ for any nonadjacent vertices u and v of G.

If G is isomorphic to the graph obtained from $K_{n-1}$ by adding one vertex joined to $t\ (2\le t\le n-1)$ vertices of $K_{n-1}$, then it’s easy to see that there is at most one edge e such that $c_{e}(G)\le n-1$, a contradiction. So there must exist four vertices, say $u_{i_{1}},u_{i_{2}},u_{i_{3}}$ and $u_{i_{4}}$, such that $u_{i_{1}}u_{i_{2}}\notin G$ and $u_{i_{3}}u_{i_{4}}\notin G$. Let $V'=\{u_{i_{1}},u_{i_{2}},u_{i_{3}},u_{i_{4}}\}$. Then

$$\begin{aligned} e(G)= & {} e(G[V'])+e(V',V(G){\setminus } V')+e(G-V')\nonumber \\= & {} \sum _{j=1}^{4}d(u_{i_{j}})-e(G[V'])+e(G-V'). \end{aligned}$$

(3.1)

Note that $d(u_{i_{1}})+d(u_{i_{2}})\le n$ and $d(u_{i_{3}})+d(u_{i_{4}})\le n$. So $\sum _{j=1}^{4}d(u_{i_{j}})\le 2n$. If $\sum _{j=1}^{4}d(u_{i_{j}})< 2n$, $e(G[V'])\ge 1$ or $e(G-V')<\left( {\begin{array}{c}n-4\\ 2\end{array}}\right)$, then by (3.1), we have that $e(G)\le 2n+\left( {\begin{array}{c}n-4\\ 2\end{array}}\right) -1=f_{3}(n,n)\le f(n,n)$. Thus, we can assume that $\sum _{j=1}^{4}d(u_{i_{j}})=2n$, $V'$ is an independent set and $G-V'\cong K_{n-4}$. If there are two vertices of $V'$, say $u_{i_{1}}$ and $u_{i_{2}}$, such that $N(u_{i_{1}})\ne N(u_{i_{2}})$, then there must exist a vertex w such that $w\in N(u_{i_{1}}){\setminus } N(u_{i_{2}})$ or $w\in N(u_{i_{2}}){\setminus } N(u_{i_{1}})$. Without loss of generality, we can assume that $w\in N(u_{i_{1}}){\setminus } N(u_{i_{2}})$. Then $V''=\{u_{i_{1}},u_{i_{2}},w,u_{i_{4}}\}$ is a vertex set with $u_{i_{1}}u_{i_{4}}\notin G$, $u_{i_{2}}w\notin G$ and $e(G[V''])\ge 1$. We may proceed as above to get that $e(G)\le f(n,n)$. Hence, we can assume that all vertices of $V'$ have the same neighborhood. Let $d(u_{i_{j}})=t$, $j=1,2,3,4$.

Now we can see that G is isomorphic to the graph obtained from $K_{n-4}$ by adding four isolated vertices each joined to the same t vertices of $K_{n-4}$. Since $\sum _{j=1}^{4}d(u_{i_{j}})=2n$, we get that $t=\frac{n}{2}$. It implies n is even, and $n\ge 8$ since $n-4\ge t$. If $n\ge 12$, then $t\ge 6$. It is easy to check that $c_{e}(G)=n$ for any edge e of G, a contradiction. If $n=8$ or 10, then $e(G)=\left( {\begin{array}{c}n-4\\ 2\end{array}}\right) +4t=\left( {\begin{array}{c}n-4\\ 2\end{array}}\right) +2n=f_{2}(n,n)\le f(n,n)$. It completes the proof of Theorem 3.3. $\square$

Proof of Theorem 1.2

Note that $F_{G}=\{e|e\in G \ \mathrm{and}\ c_{e}(G)\le k-1\}$. Suppose that G is a 2-connected graph of order n $(n\ge 6)$ such that $|F_{G}|\ge 2$. We shall prove that $e(G)\le f(n,k)$.

We apply induction on n $(n\ge k\ge 6)$. If $n=6$, then $k=6$ and $f(6,6)=12$. By Theorem 1.1, if $e(G)>f_{0}(6,6)=12$, then $F_{G}=\emptyset$. Since $|F_{G}|\ge 2$, we have that $e(G)\le 12=f(6,6)$. Assume that the result is true for those graphs of order less than n $(n>6)$. Let G be a 2-connected graph of order n such that $|F_{G}|\ge 2$.

Claim 1

If G has a 2-vertex cut $\{u,v\}$ with $uv\in E(G)$, then $e(G)\le f(n,k)$.

Assume that $G-\{u,v\}$ has s components, say $H_{i}$, $1\le i\le s\ (s\ge 2)$. Let $G_{i}=G[V(H_{i})\cup \{u,v\}]$ and $n_{i}=|V(G_{i})|$, $1\le i\le s$. We shall show that $|F_{G}\cap E(G_{i})|\ge 2$ for some i $(1\le i\le s)$.

If $c_{uv}(G)\le k-1$, then $uv\in F_{G}$. Since $|F_{G}|\ge 2$, there exists an edge $e'\in F_{G}$ and $e'\ne uv$. Without loss of generality, we can assume that $e'\in E(G_{i_{0}})$. Since $uv\in E(G_{i_{0}})$, $|F_{G}\cap E(G_{i_{0}})|\ge 2$. If $c_{uv}(G)\ge k$, then $c_{uv}(G_{j_{0}})\ge k$ for some $j_{0}$ $(1\le j_{0}\le s)$. Let C be a longest cycle which contains uv in $G_{j_{0}}$. For any edge $e\notin E(G_{j_{0}})$, say $e\in E(G_{l})$, $l\ne j_{0}$, since $G_{l}$ is 2-connected and $e\ne uv$, e and uv must lie on a common cycle $C'$ in $G_{l}$ by Menger’s Theorem. So $(C\cup C')-uv$ is a cycle containing e and with length more than k in G. Therefore, $F_{G}\subseteq E(G_{j_{0}})$. It means $|F_{G}\cap E(G_{j_{0}})|=|F_{G}|\ge 2$.

Without loss of generality, we can assume that $|F_{G}\cap E(G_{1})|\ge 2$. Choose $e_{1}$ and $e_{2}$ from $F_{G}\cap E(G_{1})$, such that $c_{(e_{1},uv)}(G_{1})=\mathrm{max} \{c_{(e,uv)}(G_{1})|e\in F_{G}\cap E(G_{1}) \}$. Clearly, $e_{1}\ne uv$ and $c_{(e_{1},uv)}(G_{1})\ge 3$. Let $G'_{1}=G-H_{1}$ and $n'_{1}=|V(G'_{1})|$. We have that $n'_{1}=n-n_{1}+2$.

If $c_{(e_{1},uv)}(G_{1})=3$, without loss of generality, we may assume that $e_{1}=uw$, then we have that $d_{G_{1}}(v)=2$. Since $c_{e_{1}}(G)\ge c_{(e_{1},uv)}(G_{1})+c_{uv}(G'_{1})-2$ and $c_{e_{1}}(G)\le k-1$, we get that $c_{uv}(G'_{1})\le k-2$. Note that $n'_{1}\ge 3$, $k-1>3$ and $G'_{1}$ is 2-connected. By Theorem 1.1,

$$\begin{aligned} e(G'_{1})\le f_{0}(n'_{1},k-1). \end{aligned}$$

If $n_{1}=3$, then

$$\begin{aligned} e(G)=e(G_{1})+e(G'_{1})-1\le \left( {\begin{array}{c}3\\ 2\end{array}}\right) +f_{0}(n'_{1},k-1)-1=f_{1}(n,k)\le f(n,k). \end{aligned}$$

If $n_{1}\ge 4$, note that $d_{G_{1}}(v)=2$, $|V(G_{1}-v)|\ge 3$ and $G_{1}-v$ is 2-connected, then $c_{(e,uv)}(G_{1})\ge 4$ for any edge $e\in E(G_{1})\backslash \{e_{1},uv\}$. By the choice of $e_{1}$, we have that $F_{G}\cap E(G_{1})\subseteq \{e_{1},uv\}$. Since $|F_{G}\cap E(G_{1})|\ge 2$, $F_{G}\cap E(G_{1})= \{e_{1},uv\}$. That is, $c_{uv}(G)\le k-1$. And since $c_{uv}(G)\ge c_{uv}(G_{1})=c_{e_{1}}(G_{1}-v)+1$, we get that $c_{e_{1}}(G_{1}-v)\le k-2$. Note that $|V(G_{1}-v)|=n_{1}-1\ge 3$ and $k-1>3$. By Theorem 1.1,

$$\begin{aligned} e(G_{1}-v)\le f_{0}(n_{1}-1,k-1). \end{aligned}$$

Thus,

$$\begin{aligned} e(G)= & {} e(G_{1})+e(G'_{1})-1 \\= & {} e(G_{1}-v)+d_{G_{1}}(v)+e(G'_{1})-1\\\le & {} f_{0}(n_{1}-1,k-1)+2+f_{0}(n'_{1},k-1)-1\\\le & {} f_{1}(n,k)\le f(n,k). \end{aligned}$$

If $c_{(e_{1},uv)}(G_{1})\ge 4$, then $c_{uv}(G'_{1})\le c_{e_{1}}(G)-c_{(e_{1},uv)}(G_{1})+2\le k-3$. Note that $n_{1}\ge 4$, $n_{1}'\ge 3$ and $k-2>3$. By Theorem 1.1,

$$\begin{aligned} e(G'_{1})\le f_{0}(n'_{1},k-2)=g(n'_{1},k), \end{aligned}$$

(3.2)

where $g(n'_{1},k)=q\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n'_{1}-2)+1$, $n'_{1}-2=q(k-5)+r$, $q\ge 0$ and $0\le r<k-5$.

We consider three cases.

Case 1  $n_{1}\ge k$.

Since $c_{e_{i}}(G_{1})\le c_{e_{i}}(G)\le k-1$ $(i=1,2)$, $|F_{G_{1}}|\ge 2$. Note that $G_{1}$ is 2-connected graph of order $n_{1}$, $k\le n_{1}<n$. By induction hypothesis, $e(G_{1})\le f(n_{1},k)$. By (3.2) and Lemma 2.6,

$$\begin{aligned} e(G)=e(G_{1})+e(G'_{1})-1\le f(n_{1},k)+g(n'_{1},k)-1\le f(n,k). \end{aligned}$$

Case 2  $n_{1}=k-1$.

If $e(G_{1})\le \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +2=\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +2(n_{1}-2)+1$, then by (3.2),

$$\begin{aligned} e(G)= & {} e(G_{1})+e(G'_{1})-1\nonumber \\\le & {} \left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +2(n_{1}-2)+1+q\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) \nonumber \\&+2(n_{1}'-2)+1-1, \end{aligned}$$

(3.3)

where $n'_{1}-2=q(k-5)+r$, $q\ge 0$ and $0\le r<k-5$. By Lemma 2.3,

$$\begin{aligned} q\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) \le q'\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) , \end{aligned}$$

(3.4)

where $n'_{1}-2=q'(k-4)+r'$, $q'\ge 0$ and $0\le r'<k-4$. Using (3.4) in (3.3),

$$\begin{aligned} e(G)\le (q'+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r'\\ 2\end{array}}\right) +2(n-2)+1=f_{1}(n,k)\le f(n,k). \end{aligned}$$

Note that $n_{1}=k-1\ge 5$. If $e(G_{1})=\left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3$, then by Theorem 3.2, $c_{(e_{1},uv)}(G_{1})\ge n_{1}-1=k-2$. Thus, $c_{uv}(G'_{1})\le c_{e_{1}}(G)-c_{(e_{1},uv)}(G_{1})+2\le (k-1)-(k-2)+2=3$. Note that $n'_{1}\ge 3$. By Theorem 1.1, $e(G'_{1})\le 2(n'_{1}-2)+1$. Thus,

$$\begin{aligned} e(G)=e(G_{1})+e(G'_{1})-1\le \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3+2(n'_{1}-2)+1-1. \end{aligned}$$

(3.5)

Using $n'_{1}=n-n_{1}+2$, $n_{1}=k-1$ and $n\ge k$ in (3.5),

$$\begin{aligned} e(G)\le & {} \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +2(n-k+1)+3\le \left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3(n-k+2)\\= & {} f_{3}(n,k)\le f(n,k). \end{aligned}$$

If $e(G_{1})>\left( {\begin{array}{c}k-2\\ 2\end{array}}\right) +3$, then by Theorem 3.2, $c_{(e_{1},uv)}(G_{1})=n_{1}=k-1$. Since $c_{uv}(G'_{1})\ge 3$, we have that $c_{e_{1}}(G)\ge c_{(e_{1},uv)}(G_{1})+c_{uv}(G'_{1})-2\ge k$. It’s a contradiction.

Case 3  $4\le n_{1}<k-1$.

If $e(G_{1})\le \left( {\begin{array}{c}n_{1}-1\\ 2\end{array}}\right) +3=\left( {\begin{array}{c}n_{1}-3\\ 2\end{array}}\right) +2(n_{1}-2)+2$, then

$$\begin{aligned} e(G)= & {} e(G_{1})+e(G'_{1})-1\nonumber \\\le & {} \left( {\begin{array}{c}n_{1}-3\\ 2\end{array}}\right) +2(n_{1}-2)+2+q\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n'_{1}-2)+1-1.\nonumber \\ \end{aligned}$$

(3.6)

If $q\ge 1$, then by Corollary 2.4,

$$\begin{aligned} (q-1)\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) \le q_{1}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) , \end{aligned}$$

(3.7)

where $(q-1)(k-5)+r=q_{1}(k-4)+r_{1}$, $q_{1}\ge 0$ and $0\le r_{1}<k-4$. Note that $0<n_{1}-3<k-4$. Then

$$\begin{aligned} \left( {\begin{array}{c}n_{1}-3\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-5\\ 2\end{array}}\right)= & {} \left( {\begin{array}{c}n_{1}-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) -((k-5)-(n_{1}-4))\nonumber \\\le & {} \left( {\begin{array}{c}n_{1}-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) -1. \end{aligned}$$

(3.8)

Since $0\le n_{1}-4<k-4$ and $0\le r_{1}<k-4$, by Lemma 2.5,

$$\begin{aligned} \left( {\begin{array}{c}n_{1}-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{1}\\ 2\end{array}}\right) \le q_{2}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) , \end{aligned}$$

(3.9)

where $(n_{1}-4)+r_{1}=q_{2}(k-4)+r_{2}$, $q_{2}\ge 0$ and $0\le r_{2}<k-4$. Using (3.7), (3.8) and (3.9) in (3.6),

$$\begin{aligned} e(G)\le & {} \left( {\begin{array}{c}n_{1}-3\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +(q-1)\left( {\begin{array}{c}k-5\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n-2)+2\nonumber \\\le & {} (q_{1}+q_{2}+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n-2)+1.\nonumber \end{aligned}$$

Clearly, $n-3=(q_{1}+q_{2}+1)(k-4)+r_{2}$. So $f_{1}(n,k)=(q_{1}+q_{2}+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{2}\\ 2\end{array}}\right) +2(n-2)+1$. Therefore, $e(G)\le f_{1}(n,k)\le f(n,k)$.

If $q=0$, then $n'_{1}-2=r$. Note that $0<r<k-4$ and $0<n_{1}-3<k-4$. By Lemma 2.5,

$$\begin{aligned} \left( {\begin{array}{c}n_{1}-3\\ 2\end{array}}\right) +\left( {\begin{array}{c}r\\ 2\end{array}}\right) <q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) , \end{aligned}$$

(3.10)

where $(n_{1}-3)+r=q_{3}(k-4)+r_{3}$, $q_{3}\ge 0$ and $0\le r_{3}<k-4$. Note that $q=0$ and $n'_{1}=n-n_{1}+2$. Using (3.10) in (3.6),

$$\begin{aligned} e(G)\le & {} \left( {\begin{array}{c}n_{1}-3\\ 2\end{array}}\right) +2(n_{1}-2)+\left( {\begin{array}{c}r\\ 2\end{array}}\right) +2(n'_{1}-2)+2\\< & {} q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) +2(n-2)+2 \\\le & {} q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) +2(n-2)+1. \end{aligned}$$

It is easy to see that $n-3=q_{3}(k-4)+r_{3}$. Hence, $f_{1}(n,k)=q_{3}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{3}\\ 2\end{array}}\right) +2(n-2)+1$. So $e(G)\le f_{1}(n,k)\le f(n,k)$.

If $e(G_{1})>\left( {\begin{array}{c}n_{1}-1\\ 2\end{array}}\right) +3$, note that $n_{1}\ge 5$ since $\left( {\begin{array}{c}4-1\\ 2\end{array}}\right) +3=\left( {\begin{array}{c}4\\ 2\end{array}}\right)$, then by Theorem 3.2, $c_{(e_{1},uv)}(G_{1})=n_{1}$. So $c_{uv}(G'_{1})\le c_{e_{1}}(G)-c_{(e_{1},uv)}(G_{1})+2\le (k-1)-n_{1}+2=k-n_{1}+1$. Since $n_{1}<k-1$, $k-n_{1}+2>3$. By Theorem 1.1,

$$\begin{aligned} e(G'_{1})\le f_{0}(n_{1}',k-n_{1}+2). \end{aligned}$$

Let $f_{0}(n_{1}',k-n_{1}+2)=q_{4}\left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{4}\\ 2\end{array}}\right) +2(n_{1}'-2)+1$, where $n_{1}'-2=q_{4}(k-n_{1}-1)+r_{4}$, $q_{4}\ge 0$ and $0\le r_{4}<k-n_{1}-1$. Since $n_{1}'-2=n-n_{1}\ge k-n_{1}$, $q_{4}\ge 1$. Then

$$\begin{aligned} e(G)= & {} e(G_{1})+e(G'_{1})-1\nonumber \\\le & {} \left( {\begin{array}{c}n_{1}\\ 2\end{array}}\right) +\left[ q_{4}\left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{4}\\ 2\end{array}}\right) +2(n'_{1}-2)+1\right] -1\nonumber \\= & {} \left[ \left( {\begin{array}{c}n_{1}-2\\ 2\end{array}}\right) +2(n_{1}-2)+1\right] \nonumber \\&+\left[ \left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) +(q_{4}-1)\left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{4}\\ 2\end{array}}\right) +2(n'_{1}-2)\right] \end{aligned}$$

(3.11)

Since $4\le n_{1}<k-1$, $0<k-n_{1}-1<k-4$. By Corollary 2.4,

$$\begin{aligned} (q_{4}-1)\left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{4}\\ 2\end{array}}\right) \le q_{5}\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{5}\\ 2\end{array}}\right) , \end{aligned}$$

(3.12)

where $(q_{4}-1)(k-n_{1}-1)+r_{4}=q_{5}(k-4)+r_{5}$, $q_{5}\ge 0$ and $0\le r_{5}<k-4$. If $4\le n_{1}<k-2$, then $0<n_{1}-2<k-4$ and $0<k-n_{1}-1<k-4$. By Lemma 2.5,

$$\begin{aligned} \left( {\begin{array}{c}n_{1}-2\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) \le \left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}1\\ 2\end{array}}\right) =\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) . \end{aligned}$$

(3.13)

If $n_{1}=k-2$, then $\left( {\begin{array}{c}n_{1}-2\\ 2\end{array}}\right) +\left( {\begin{array}{c}k-n_{1}-1\\ 2\end{array}}\right) = \left( {\begin{array}{c}k-4\\ 2\end{array}}\right)$. It means (3.13) holds for $4\le n_{1}<k-1$. Using (3.12) and (3.13) in (3.11),

$$\begin{aligned} e(G)\le (q_{5}+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{5}\\ 2\end{array}}\right) +2(n-2)+1. \end{aligned}$$

Clearly, $n-3=(q_{5}+1)(k-4)+r_{5}$. So $f_{1}(n,k)=(q_{5}+1)\left( {\begin{array}{c}k-4\\ 2\end{array}}\right) +\left( {\begin{array}{c}r_{5}\\ 2\end{array}}\right) +2(n-2)+1$. That is, $e(G)\le f_{1}(n,k)\le f(n,k)$. It completes the proof of Case 3, and so the proof of Claim 1.

Claim 2

Let $e_{1},\ e_{2}\in F_{G}$, $uv\in E(G)$ and $uv\ne e_{i}$ $(i=1,2)$. If $N_{G}(u)\cap N_{G}(v)=\emptyset$, then $e(G)\le f(n,k)$.

If $k=n$, then by Theorem 3.3, $e(G)\le f(n,n)$. So we can assume that $6\le k\le n-1$. Let $G'=G/uv$. We identify u and v with a new vertex w in $G'$. If $e_{i}$ $(i=1,2)$ is not incident with u and v, then clearly $c_{e_{i}}(G')\le c_{e_{i}}(G)\le k-1$. If $e_{i}=ux$ (or vy), $i=1,2$, where $x\in N(u)-\{v\}$ ($y\in N(v)-\{u\}$), then it’s easy to see that $c_{wx}(G')\le c_{ux}(G)\le k-1$ ($c_{wy}(G')\le c_{vy}(G)\le k-1$). So $|F_{G'}|\ge 2$. Since $|V(G')|=n-1>3$, $G'$ isn’t isomorphic to $K_{3}$. By Claim 1 and Lemma 2.2, $G'$ is 2-connected. Note that $|V(G')|=n-1$, and $6\le k\le n-1$. Then by induction hypothesis, $e(G')\le f(n-1,k)$. Thus, $e(G)=e(G')+1\le f(n-1,k)+1\le f(n,k)$. It completes the proof of Claim 2.

Let $\mathcal{G}=\{G|G$ is 2-connected graph of order n with $|F_{G}|\ge 2\}$, and $m^{*}=\mathrm{max}\{e(G)|G\in \mathcal{G}\}$. We only need to show that $m^{*}\le f(n,k)$. For $G\in \mathcal{G}$, let $F_{G}=\{e_{1},e_{2},\dots ,e_{l}\}$, where $e_{i}=u_{i}v_{i}$ for $1\le i\le l$. We define $l_{(e,e')}(G)$ to be the minimum length of cycles containing e and $e'$ in G. Let $l(G)=\mathrm{min}\{l_{(e_{i},e_{j})}(G)|e_{i},e_{j}\in F_{G},\ 1\le i<j\le l\}$. Now we choose $G_{a}\in \mathcal{G}$ and $e(G_{a})=m^{*}$, and subject to this, let $l(G_{a})$ be as small as possible. By Claim 1, we can assume that $G_{a}$ has no vertex cut $\{u,v\}$ with $uv\in G_{a}$. We shall show that $l(G_{a})=3$.

Since $G_{a}$ is 2-connected, any two distinct edges must lie on a common cycle by Menger’s theorem. So $l(G_{a})\ge 3$. Without loss of generality, we may assume that $l_{(e_{1},e_{2})}(G_{a})=l(G_{a})$. Let C be a cycle containing $e_{1}$ and $e_{2}$ with $e(C)=l(G_{a})$. If $l(G_{a})\ge 4$, then let xy be an edge of C with $xy\ne e_{i}$ for $i=1,2$. If $N_{G_{a}}(x)\cap N_{G_{a}}(y)=\emptyset$, then by Claim 2, $e(G_{a})\le f(n,k)$; otherwise, we do edge-switching from y to x in $G_{a}$. Let $G_{a}'=G_{a}[y\rightarrow x]$. Then by Lemma 2.2 and our assumption, we have that $G_{a}'$ is 2-connected. If y is not incident with $e_{1}$ and $e_{2}$, then by Lemma 2.1 (a) and (c), we get that $c_{e_{i}}(G_{a}')\le c_{e_{i}}(G_{a})\le k-1$, for $i=1,2$. Let $x'$ be another neighbor of y in C. Note that $xx'\notin G_{a}$ by the choice of C. Then $C'=(C-\{y\})\cup \{xx'\}$ is a cycle containing $e_{1}$ and $e_{2}$ in $G_{a}'$ with $e(C')<e(C)$. So $l(G_{a}')\le l_{(e_{1},e_{2})}(G_{a}')<l_{(e_{1},e_{2})}(G_{a})=l(G_{a})$. If y is an endvertex of some $e_{i}$ $(i=1,2)$, say $e_{2}$ ($e_{2}=u_{2}v_{2}$) and $y=u_{2}$, then by Lemma 2.1, $c_{e_{1}}(G_{a}')\le c_{e_{1}}(G_{a})\le k-1$. Considering the edge $e_{2}=yv_{2}$, it follows from Lemma 2.1 (b) that $c_{xv_{2}}(G_{a}')\le c_{yv_{2}}(G_{a})= c_{e_{2}}(G_{a})\le k-1$ since $v_{2}\in N_{G_{a}}(y)\backslash \{x\}$. It is easy to see that $(C-\{y\})\cup \{xv_{2}\}$ is a cycle containing $e_{1}$ and $xv_{2}$ in $G_{a}'$. So $l(G_{a}')\le l_{(e_{1},\ xv_{2})}(G_{a}')<l_{(e_{1},e_{2})}(G_{a})=l(G_{a})$. In either case, we have that $|F_{G'_{a}}|\ge 2$ and $l(G_{a}')<l(G_{a})$, which contradicts to our choice of $G_{a}$. Hence, $l(G_{a})=3$.

Let $\mathcal{G'}=\{G|G\in \mathcal{G},\ e(G)=m^{*}\ \mathrm{and}\ l(G_{a})=3\}$. By the discussion above, we know that $\mathcal{G'}\ne \emptyset$. For $G\in \mathcal{G'}$, define $q(G)=\mathrm{max}\{d(u)|u\in G\ \mathrm{and}\ u\ \mathrm{is\ a\ common\ endvertex\ of}\ e_{i}$ $\ \mathrm{and}\ e_{j}, \mathrm{where}\ e_{i},e_{j}\in F_{G}, \mathrm{and}\ l(e_{i},e_{j})=3, 1\le i<j\le l\}$. Choose $G_{b}\in \mathcal{G'}$ such that $q(G_{b})$ is as large as possible. By Claim 1, we may assume that $G_{b}$ has no vertex cut $\{u,v\}$ with $uv\in G_{b}$. We shall show that $q(G_{b})=n-1$.

Without loss of generality, we may assume that $l(e_{1},e_{2})=l(G_{b})=3$, $u_{1}=u_{2}=u$, and $d_{G_{b}}(u)=q(G_{b})$. Clearly, $v_{1}v_{2}\in G_{b}$. If $d_{G_{b}}(u)<n-1$, then there exists a vertex z such that $uz\notin G_{b}$. Since $\{v_{1},v_{2}\}$ is not a vertex cut of $G_{b}$ by our assumption, there must exist a path from u to z, which doesn’t pass through $v_{1}$ and $v_{2}$. Let $P=uz_{2}z_{3}\ldots z_{t}z$ $(t\ge 2)$ be a shortest path from u to z with $v_{i}\notin P$ $(i=1,2)$. Clearly, $uz_{3}\notin G_{b}$. If $N_{G_{b}}(u)\cap N_{G_{b}}(z_{2})=\emptyset$, then by Claim 2, $e(G_{b})\le f(n,k)$; otherwise, let $G_{b}'=G_{b}[z_{2}\rightarrow u]$. By Lemma 2.2 and our assumption, we get that $G_{b}'$ is 2-connected. By Lemma 2.1 (a), $c_{e_{i}}(G_{b}')\le c_{e_{i}}(G_{b})\le k-1$, for $i=1,2$. That is, $|F_{G_{b}'}|\ge 2$. Since $v_{1}v_{2}\in G_{b}'$, we have that $l_{(e_{1},e_{2})}(G_{b}')=3$, which implies that $l(G_{b}')=3$. It’s also easy to see that $e(G_{b}')=e(G_{b})=m^{*}$, and $N_{G_{b}}(u)\subset N_{G_{b}'}(u)$ since $z_{3}\in N_{G_{b}}(z_{2}){\setminus } (N_{G_{b}}(u)\cup \{u\})$. Therefore, $G_{b}'\in \mathcal{G'}$ and $q(G_{b}')\ge d_{G_{b}'}(u)>d_{G_{b}}(u)=q(G_{b})$, a contradiction. Hence, $d_{G_{b}}(u)=n-1$.

Now $G_{b}$ is a 2-connected graph of n vertices and $m^{*}$ edges, $c_{uv_{i}}(G_{b})\le k-1$ $(i=1,2)$, $v_{1}v_{2}\in G_{b}$ and $d_{G_{b}}(u)=n-1$. Let $G_{b}''=G_{b}-u$. If $G_{b}''$ has a cut vertex w, then $\{u,w\}$ is a vertex cut of $G_{b}$ with $uw\in G_{b}$. It contradicts to our assumption. So $G_{b}''$ is 2-connected. Let $C''$ be a longest cycle of $G_{b}''$. We shall show that $e(C'')< k-1$. Let $P''$ be a path from $v_{1}$ to $C''$ in $G_{b}''$, and let $w'$ be the first vertex of $P''$ on $C''$. Note that $w'=v_{1}$ when $v_{1}\in C''$. Then $C'''=uv_{1}\overrightarrow{P''}w'\overrightarrow{C}w'^{-}u$ is a cycle containing $e_{1}=uv_{1}$ with $e(C''')>e(C'')$ in $G_{b}$, where $w'^{-}$ is the vertex on $C''$ immediately before $w'$ according to the orientation of $C''$. Then $e(C'')<e(C''')\le c_{uv_{1}}(G_{b})\le k-1$. By Theorem 3.1, we get that $e(G_{b}'')\le t(n-1,k-2)$. Hence,

$$\begin{aligned} m^{*}= & {} e(G_{b})=e(G_{b}'')+d(u)\le t(n-1,k-2)+(n-1)\\= & {} \mathrm{max}\{f_{2}(n,k),f_{3}(n,k)\}\le f(n,k). \end{aligned}$$

This ends the proof of Theorem 1.2. $\square$