Long Paths and Cycles Passing Through Specified Vertices Under the Average Degree Condition

Abstract

Let $G$ be a $k$-connected graph with $k\ge 2$. In this paper we first prove that: For two distinct vertices $x$ and $z$ in $G$, it contains a path connecting $x$ and $z$ which passes through its any $k-2$ specified vertices with length at least the average degree of the vertices other than $x$ and $z$. Further, with this result, we prove that: If $G$ has $n$ vertices and $m$ edges, then it contains a cycle of length at least $2m/(n-1)$ passing through its any $k-1$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition.

1 Introduction

We use Bondy and Murty [2] for terminology and notations not defined here and consider finite simple graphs only.

Let $G$ be a graph and $H$ a subgraph of $G$. We use $V(H)$ and $E(H)$ to denote the set of vertices and edges of $H$, respectively, and use $e(H)$ for the number of the edges of $H$. For a vertex $v\in V(G)$, $N_H(v)$ denotes the set, and $d_H(v)$ the number, of neighbors of $v$ in $H$. We call $d_H(v)$ the degree of $v$ in $H$. Let $x$ and $z$ be two distinct vertices of $G$. A path connecting $x$ and $z$ is called an $(x,z)$-path. For a subset $Y$ of $V(G)$, an $(x,z)$-path passing through all the vertices in $Y$ is called an $(x,Y,z)$-path, and a cycle passing through all the vertices in $Y$ is called a $Y$-cycle. If $Y$ contains only one vertex $y$, an $(x,\{y\},z)$-path and a $\{y\}$-cycle are simply denoted by an $(x,y,z)$-path and a $y$-cycle, respectively. The distance between $x$ and $z$ in $H$, denoted by $d_H(x,z)$, is the length of a shortest $(x,z)$-path with all its internal vertices in $H$. If no such a path exists, we define $d_H(x,z)=\infty$. The codistance between $x$ and $z$ in $H$, denoted by $d^*_H(x,z)$, is the length of a longest $(x,z)$-path with all its internal vertices in $H$. If no such a path exists, we define $d^*_H(x,z)=0$. We remark that in the definitions of $d_H(x,z)$ and $d_H^*(x,z)$, the vertices $x$ and $z$ is not necessarily in $H$. When no confusion occurs, we use $N(v)$, $d(v)$, $d(x,z)$ and $d^*(x,z)$ instead of $N_G(v)$, $d_G(v)$, $d_G(x,z)$ and $d^*_G(x,z)$, respectively.

Long path and cycle problems are interesting and important in graph theory and have been deeply studied, see [1, 7]. The following theorem by Erdős and Gallai [5] opened the study on long paths with specified end vertices.

Theorem 1

(Erdős and Gallai [5]) Let $G$ be a 2-connected graph and $x$ and $z$ be two distinct vertices of $G$. If $d(v)\ge d$ for every vertex $v\in V(G)\backslash \{x,z\}$, then $G$ contains an $(x,z)$-path of length at least $d$.

Theorem 1 has a stronger extension due to Enomoto [4].

Theorem 2

(Enomoto [4]) Let $G$ be a 2-connected graph and $x$ and $z$ be two distinct vertices of $G$. If $d(v)\ge d$ for every vertex $v\in V(G)\backslash \{x,z\}$, then for every given vertex $y\in V(G)\backslash \{x,z\}$, $G$ contains an $(x,y,z)$-path of length at least $d$.

Another direction of extending Theorem 1 is to weaken the minimum degree condition to the average degree condition. Fan [6] finished this work as follows.

Theorem 3

(Fan [6]) Let $G$ be a 2-connected graph and $x$ and $z$ be two distinct vertices of $G$. If the average degree of the vertices other than $x$ and $z$ is at least $r$, then $G$ contains an $(x,z)$-path of length at least $r$.

The following graph shows that one cannot replace the minimum degree condition in Theorem 2 by the average degree condition. Let $H$ be the complete graph on $n-1$ vertices and $x,z\in V(H)$, and $G$ be the graph obtained from $H$ by adding a new vertex $y$ and two edges $xy,yz$. Then the length of the longest $(x,y,z)$-path in $G$ is 2, less than the average degree of the vertices other than $x$ and $z$ when $n\ge 5$.

Our first result in this paper is a generalization of Theorem 3.

Theorem 4

Let $G$ be a $k$-connected graph with $k\ge 2$, and $x$ and $z$ be two distinct vertices of $G$. If the average degree of the vertices other than $x$ and $z$ is at least $r$, then for any subset $Y$ of $V(G)$ with $|Y|= k-2$, $G$ contains an $(x,Y,z)$-path of length at least $r$.

We remark here that the size of $Y$ cannot be replaced by $k-1$. Let $H$ be a complete graph on $n-k+1$ vertices with $n>3k$ and $u_1=x,u_2,\ldots ,u_k=z$ be $k$ vertices of $H$, and $Y=\{y_1,y_2,\ldots ,y_{k-1}\}$ be a set of vertices not in $V(H)$. We construct a graph $G$ with $V(G)=V(H)\cup Y$ and $E(G)=E(H)\cup \{u_iy_j:1\le i\le k, 1\le j\le k-1\}$. Then $G$ is a $k$-connected graph and the longest $(x,Y,z)$-path has length $2k-1$, which is less than

$$\begin{aligned} \frac{\sum _{v\in V(G)\backslash \{x,z\}}d(v)}{n-2}&=\,\frac{(k-1)k+(k-2)(n-1)+(n-2k+1)(n-k)}{n-2}\\&=\,\frac{n^2-2kn+n+3k^2-3k}{n-2}. \end{aligned}$$

Besides, the complete graph $K_n$ with $n\ge k+1$ shows that the bound $r$ on the length of the $(x,Y,z)$-path is sharp.

There also exist results on long cycles passing through specified vertices in graphs. Theorem 5 shows the existence of long cycles in 2-connected graph under the minimum degree condition, and Theorem 6 extends Theorem 5 to graphs with higher connectivity.

Theorem 5

(Locke [8]) Let $G$ be a 2-connected graph. If the minimum degree of $G$ is at least $d$, then for any two vertices $y_1$ and $y_2$ of $G$, $G$ contains either a $\{y_1,y_2\}$-cycle of length at least $2d$ or a Hamilton cycle.

Theorem 6

(Egawa et al. [3]) Let $G$ be a $k$-connected graph with $k\ge 2$. If the minimum degree of $G$ is at least $d$, then for any subset $Y$ of $V(G)$ with $|Y|=k$, $G$ contains either a $Y$-cycle of length at least $2d$ or a Hamilton cycle.

On the existence of long cycles in graphs with a given number of edges, Erdős and Gallai [5] gave the following result.

Theorem 7

(Erdős and Gallai [5]) Let $G$ be a 2-edge-connected graph on $n$ vertices. Then $G$ contains a cycle of length at least $2e(G)/(n-1)$.

In this paper, as an application of Theorem 4, we give the following theorem on long cycles passing through specified vertices of graphs with a given number of vertices and edges.

Theorem 8

Let $G$ be a $k$-connected graph on $n$ vertices with $k\ge 2$. Then for any subset $Y$ of $V(G)$ with $|Y|=k-1$, $G$ contains a $Y$-cycle of length at least $2e(G)/(n-1)$.

In Theorem 8, one cannot expect a cycle passing through $k$ specified vertices of length at least $2e(G)/(n-1)$. Let $H$ be a complete graph on $n-k$ vertices with $n>3k$ and $u_1,u_2,\ldots ,u_k$ be $k$ vertices of $H$, and $Y=\{v_1,v_2,\ldots ,v_k\}$ be a set of vertices not in $V(H)$. We construct a graph $G$ with $V(G)=V(H)\cup Y$ and $E(G)=E(H)\cup \{u_iv_j:1\le i,j\le k\}$. Then $G$ is a $k$-connected graph and the longest $Y$-cycle has length $2k$, which is less than

$$\begin{aligned} \frac{2e(G)}{n-1}=\frac{(n-k)(n-k-1)+2k^2}{n-1}. \end{aligned}$$

In the following section we will give some further notations and preliminary results that will be used later. The proofs of Theorems  4 and  8 are given in Sects. 3 and 4, respectively.

2 Preliminaries

Let $G$ be a graph and $P$, $H$ two disjoint subgraphs of $G$. We use $E(P,H)$ to denote the set, and $e(P,H)$ the number, of edges with one vertex in $P$ and the other in $H$. If $E(P,H)\ne \emptyset$, then we call $P$ and $H$ are joined. We use $N_P(H)$ to denote the set of vertices in $P$ which are joined to $H$. If $x$ is a vertex in $G-P$, we say that $x$ is locally $k$-connected to $P$ (in $G$) if there are $k$ paths connecting $x$ and vertices in $P$ such that any two of them have only the vertex $x$ in common. We say that $H$ is locally $k$-connected to $P$ (in $G$) if for every vertex $x\in V(H)$, $x$ is locally $k$-connected to $P$. Note that if $H$ is locally $k$-connected to $P$, then $H$ is locally $l$-connected to $P$ for all $l$, $0\le l\le k$; and, if $G$ is $k$-connected and $|V(P)|\ge k$, then $H$ is locally $k$-connected to $P$ in $G$.

The following propositions on local $k$-connectedness are proved in [6].

Proposition 1

(Fan [6]) Let $H$ and $P$ be two disjoint subgraphs of a graph $G$. If $H$ is locally $k$-connected to $P$ in the subgraph induced by $V(H)\cup V(P)$, then $E(P,H)$ contains an independent set of $t$ edges, where $t\ge \min \{k,|V(H)|\}$.

Proposition 2

(Fan [6]) Let $H$ and $P$ be two disjoint subgraphs of a graph G. Let $u\in N_P(H)$ and $G^{\prime }$ be the graph obtained from $G$ by deleting all edges from $u$ to $H$. If $H$ is locally $k$-connected to $P$ in $G$, then $H$ is locally $(k-1)$-connected to $P$ in $G^{\prime }$.

Proposition 3

(Fan [6]) Let $H$ and $P$ be two disjoint subgraphs of a graph $G$, and $B$ a block of $H$. Let $H^{\prime }$ be the subgraph obtained from $H$ by contracting $B$. If $H$ is locally $k$-connected to $P$ in $G$, then $H^{\prime }$ is also locally $k$-connected to $P$ in the resulting graph.

Next we introduce the concept of local maximality for paths.

Let $P$ be a path of a graph $G$, and $u,v\in V(P)$. We use $P[u,v]$ to denote the segment of $P$ from $u$ to $v$, and $P(u,v)$ the segment obtained from $P[u,v]$ by deleting the two end vertices $u$ and $v$. Let $H$ be a component of $G-P$. We say that $P$ is a locally longest path with respect to $H$ if we cannot obtain a longer path than $P$ by replacing the segment $P[u,v]$ by a $(u,v)$-path with all its internal vertices in $H$ for any $u,v\in V(G)$. In other words, $P$ is locally longest with respect to $H$ if, for any $u,v\in V(P)$,

$$\begin{aligned} e(P[u,v])\ge d_H^*(u,v). \end{aligned}$$

If $P$ is an $(x,Y,z)$-path of $G$, where $x,z\in V(G)$ and $Y\subset V(G)$, then we say that $P$ is a locally longest $(x,Y,z)$-path with respect to $H$ if we cannot obtain an $(x,Y,z)$-path longer than $P$ by replacing the segment $P[u,v]$ with $Y\cap V(P(u,v))=\emptyset$ by a $(u,v)$-path with all its internal vertices in $H$. Note that if $P$ is a longest path [longest $(x,Y,z)$-path] in a graph $G$, then, of course, $P$ is a locally longest path [locally longest $(x,Y,z)$-path] with respect to any component of $G-P$. If two vertices $u$ and $u^{\prime }$ in $V(P)$ are joined to $H$ by two independent edges, then we call $\{u,u^{\prime }\}$ a strong attached pair of $H$ to $P$. A strong attachment of $H$ to $P$ (in $G$) is a subset $T=\{u_1,u_2,\ldots ,u_t\}\subset N_P(H)$, where $u_i$, $1\le i\le t$, are in order along $P$, such that each ordered pair $\{u_i,u_{i+1}\}$, $1\le i\le t-1$, is a strong attached pair of $H$ to $P$. A strong attachment $T$ of $H$ to $P$ is maximum if $T$ has maximum cardinality over all strong attachments of $H$ to $P$.

The following result due to Fan is useful in our proofs.

Lemma 1

(Fan [6]) Let $G$ be a graph and $P$ an $(x,z)$-path of $G$. Suppose that $H$ is a component of $G-P$ and $T=\{u_1,u_2,\ldots ,u_t\}$ is a maximum strong attachment of $H$ to $P$. Set $S=N_P(H)\backslash T$. Then the following statements are true:

• (1) Every vertex in $S$ is adjacent to exactly one vertex in $H$.

• (2) For each segment $P[u_i,u_{i+1}]$, $1\le i\le t-1$, suppose that

  $$\begin{aligned} N_P(H)\cap V(P[u_i,u_{i+1}])=\{a_0,a_1,\ldots ,a_q,a_{q+1}\}, \end{aligned}$$

  where $a_0=u_i$, $a_{q+1}=u_{i+1}$ and $a_j$, $0\le j\le q+1$, are in order along $P$. Then there is a subscript $m$, $0\le m\le q$, such that

  $$\begin{aligned} N_H(a_j)=N_H(a_0),\quad \text{ for } \,0\le j\le m, \end{aligned}$$

  and

  $$\begin{aligned} N_H(a_j)=N_H(a_{q+1}), \quad \text{ for } \,m+1\le j\le q+1. \end{aligned}$$

  Besides, if

  $$\begin{aligned} N_P(H)\cap V(P[x,u_1])=\{a_1,\ldots ,a_q,a_{q+1}\}, \end{aligned}$$

  where, $a_{q+1}=u_1$, then

  $$\begin{aligned} N_H(a_j)=N_H(a_{q+1}), \quad \text{ for } \,1\le j\le q+1; \end{aligned}$$

  and if

  $$\begin{aligned} N_P(H)\cap V(P[u_t,z])=\{a_0,a_1,\ldots ,a_q\}, \end{aligned}$$

  where, $a_0=u_t$, then

  $$\begin{aligned} N_H(a_j)=N_H(a_0), \quad \text{ for } \,0\le j\le q. \end{aligned}$$

• (3) If $H$ is locally $k$-connected to $P$ in $G$, then

  $$\begin{aligned} t\ge \min \{k,h+d_2\}, \end{aligned}$$

  where $h=|V(H)|$ and $d_2$ is the number of vertices in $N_P(H)$ each of which has at least two neighbors in $H$.

Lemma 1 (2) is somewhat different from that in [6], but the proofs of them are similar.

For a path $P$, we use $l(P)$ to denote the length of $P$.

Lemma 2

Let $G$ be a graph, $P$ an $(x,Y,z)$-path of $G$, where $x,z\in V(G)$ and $Y\subset V(G)$, $H$ a component of $G-P$ and $T=\{u_1,u_2,\ldots ,u_t\}$ a maximum strong attachment of $H$ to $P$. Set $S=N_P(H)\backslash T \text{ and } s=|S|$. Suppose that $P$ is a locally longest $(x,Y,z)$-path with respect to $H$, and $\theta =|\{x,z\}\cap N_P(H)|$. Set

$$\begin{aligned} T_r=\{u_i\in T\backslash \{u_t\}: Y\cap V(P(u_i,u_{i+1}))=\emptyset \} \quad \text{ and } \quad t_r=|T_r|. \end{aligned}$$

Then

$$\begin{aligned} l(P)\ge \sum _{u_i\in T_r}d_H^*(u_i,u_{i+1})+2(s+t-t_r)-\theta . \end{aligned}$$

Proof

If $t=0$, then $s=0$ and the statement is trivially true. Suppose now that $t\ge 1$.

Consider a segment $P[u_i,u_{i+1}]$, $1\le i \le t-1$. Suppose that

$$\begin{aligned} N_P(H)\cap V(P[u_i,u_{i+1}])=\{a_0,a_1,\ldots ,a_q,a_{q+1}\}, \end{aligned}$$

where $q=|S\cap V(P[u_i,u_{i+1}])|$, $a_0=u_i$, $a_{q+1}=u_{i+1}$, and $a_j$, $0\le j\le q+1$, are in order along $P$.

If $Y\cap V(P(u_i,u_{i+1}))=\emptyset$, then by Lemma 1 (2), there is a subscript $m$, $0\le m\le q$, such that

$$\begin{aligned} N_H(a_0)=N_H(a_m)\quad \text{ and } \quad N_H(a_{q+1})=N_H(a_{m+1}). \end{aligned}$$

Therefore

$$\begin{aligned} d_H^*(a_m,a_{m+1})=d_H^*(a_0,a_{q+1})=d_H^*(u_i,u_{i+1}). \end{aligned}$$

Since $P$ is a locally longest $(x,Y,z)$-path with respect to $H$, we have

$$\begin{aligned} l(P[u_i,u_{i+1}])&\ge \sum _{j=0}^qd_H^*(a_j,a_{j+1})=d_H^*(a_m,a_{m+1})+ \sum _{^{j=0}_{j\ne m}}^qd_H^*(a_j,a_{j+1})\\&=d_H^*(u_i,u_{i+1})+ \sum _{^{j=0}_{j\ne m}}^qd_H^*(a_j,a_{j+1}). \end{aligned}$$

Note that $d^*_H(a_j,a_{j+1})\ge 2$, for every $j$, $0\le j\le q$, we have

$$\begin{aligned} l(P[u_i,u_{i+1}])\ge d_H^*(u_i,u_{i+1})+2q. \end{aligned}$$

If $Y\cap V(P(u_i,u_{i+1}))\ne \emptyset$, then noting that $l(P[a_j,a_{j+1}])\ge 2$, we have

$$\begin{aligned} l(P[u_i,u_{i+1}])=\sum _{j=0}^ql(P[a_j,a_{j+1}])\ge 2q+2. \end{aligned}$$

Besides, consider the two segments $P[x,u_1]$ and $P[u_t,z]$. Suppose that

$$\begin{aligned} N_P(H)\cap V(P[x,u_1])=\{a_0,a_1,\ldots ,a_m\} \end{aligned}$$

and

$$\begin{aligned} N_P(H)\cap V(P[u_t,z])=\{a_{m+1},a_{m+2},\ldots ,a_{q+1}\}, \end{aligned}$$

where $m=|S\cap V(P[x,u_1])|$, $q-m=|S\cap V(P[u_t,z])|$, $a_m=u_1$, $a_{m+1}=u_t$, and $a_j$, $0\le j\le q+1$ are in order along $P$. Note that $l(P[x,a_0])+l(P[a_{q+1},z])\ge 2-\theta$ and $l(P[a_j,a_{j+1}])\ge 2$, for every $0\le j\le q$, and $j\ne m$, we have

$$\begin{aligned} l(P[x,u_1])+l(P[u_t,z])\ge 2q+2-\theta . \end{aligned}$$

Thus summing over the lengths of all the segments, yields

$$\begin{aligned} l(P)= & {} l(P[x,u_1])+\sum _{i=1}^{t-1}l(P[u_i,u_{i+1}])+l(P[u_t,z])\\\ge & {} 2(|S\cap V(P[x,u_1])|+|S\cap V(P[u_t,z])|)+2-\theta \\&+\sum _{^{~i=1}_{u_i\in T_r}}^{t-1}(d_H^*(u_i,u_{i+1})+2|S\cap V(P[u_i,u_{i+1}])|)\\&+\sum _{^{~i=1}_{u_i\notin T_r}}^{t-1}(2|S\cap V(P[u_i,u_{i+1}])|+2)\\= & {} \sum _{u_i\in T_r}d_H^*(u_i,u_{i+1})+2(s+t-t_r)-\theta . \end{aligned}$$

This ends the proof.

For a strong attachment $T=\{u_1,u_2,\ldots ,u_t\}$, the pairs $\{u_j,u_{j+1}\}$, $1\le j\le t-1$, are called strong attached pairs supported by $T$, and we call a strong attached pair $\{u_j,u_{j+1}\}$ of $H$ to $P$ transitive if $Y\cap V(P(u_j,u_{j+1}))=\emptyset$.

A connected graph is separable if it has at least one cut-vertex.

Lemma 3

Let $G$ be a graph and $P$ an $(x,z)$-path of $G$. Suppose that $H$ is a separable component of $G-P$, $B$ is an endblock of $H$, $b$ is the cut vertex of $H$ contained in $B$, and $M=B-b$. Let $T=\{u_1,u_2,\ldots ,u_t\}$ be a maximum strong attachment of $H$ to $P$. If $H$ is locally $k$-connected to $P$, then

• (1) $|N_P(M)\cap T|\ge \min \{k-1,m+d^{\prime }_2\}$; and

• (2) there exist at least $\min \{k-1,m+d^{\prime }_2\}$ strong attached pairs supported by $T$ which are joined to $M$,

where $m=|V(M)|$ and $d^{\prime }_2$ is the number of vertices in $N_P(M)$ each of which has at least two neighbors in $H$.

Proof

Since $H$ is locally $k$-connected to $P$, $|V(P)|\ge k$. It is easy to know that $M$ is locally $(k-1)$-connected to $P$ in the subgraph induced by $V(P)\cup V(M)$. By Proposition 1, there are $\min \{k-1,m\}$ independent edges in $E(P,M)$. Let $v_iw_i$, $1\le i\le \min \{k-1,m\}$ be such edges, where $v_i\in V(P)$ and $w_i\in V(M)$.

If $v_i$ has at least two neighbors in $H$, then by Lemma 1 (1), $v_i\in T$. If $v_i$ has only one neighbor $w_i$ in $H$, then by Lemma 1 (2), there exists a vertex $v^{\prime }_i$ (maybe equal to $v_i$) in $T$ which also has only one neighbor $w_i$ in $H$. This implies that $|N_P(M)\cap T|\ge \min \{k-1,m\}$.

Now, we prove (1) by induction on $d^{\prime }_2$. If $d^{\prime }_2=0$, then by the analysis above, the assertion is true. Thus we assume that $d^{\prime }_2\ge 1$.

Let $u_j$ be a vertex in $N_P(M)$ which has at least two neighbors in $H$ [$u_j$ is of course in $T$ by Lemma 1 (1)]. Let $G^{\prime }$ be the graph obtained from $G$ by deleting all edges from $u_j$ to $H$. By Proposition 2, $H$ is locally $(k-1)$-connected to $P$ in $G^{\prime }$.

If $u_j=u_1$ or $u_t$, or $\{u_{j-1},u_{j+1}\}$ is joined to $H$ by two independent edges, then $T^{\prime }=T\backslash \{u_j\}$ is a strong attachment of $H$ to $P$ in $G^{\prime }$. Since $u_j$ is joined to at least two vertices of $H$ in $G$, any strong attachment of $H$ to $P$ in $G^{\prime }$ together with $u_j$ is a strong attachment of $H$ to $P$ in $G$. Since $|T^{\prime }|=t-1$, we see that $T^{\prime }$ is a maximum strong attachment of $H$ to $P$ in $G^{\prime }$. By the induction hypothesis,

$$\begin{aligned} |N_P(M)\cap T^{\prime }|\ge \min \{k-2,m+d^{\prime }_2-1\}. \end{aligned}$$

Therefore

$$\begin{aligned} |N_P(M)\cap T|\ge \min \{k-1,m+d^{\prime }_2\}, \end{aligned}$$

as required.

If $u_j\in \{u_2,\ldots ,u_{t-1}\}$, and $\{u_{j-1},u_{j+1}\}$ are not joined to $H$ by two independent edges, i.e.,

$$\begin{aligned} N_H(u_{j-1})=N_H(u_{j+1})=\{w\}, \end{aligned}$$

for some $w\in V(H)$, then

$$\begin{aligned} T^{\prime }=T\backslash \{u_j,u_{j+1}\}=\{u_1,\ldots ,u_{j-1},u_{j+2},\ldots ,u_t\} \end{aligned}$$

is a strong attachment of $H$ to $P$ in $G^{\prime }$. We prove now that $T^{\prime }$ is maximum by showing that any strong attachment of $H$ to $P$ in $G^{\prime }$ has cardinality at most $t-2=|T^{\prime }|$.

Let $v_1,v_2$ ($\ne u_j$) be the two vertices in $N_P(H)$ which are closest to $u_j$ on $P$, say $v_1$ preceding, and $v_2$ following, $u_j$ on $P$ (but not necessarily adjacent to $u_j$ on $P$). Since $|N_H(u_j)|\ge 2$, it follows from Lemma 1 (2) that

$$\begin{aligned} N_H(v_1)=N_H(u_{j-1})=\{w\}=N_H(u_{j+1})=N_H(v_2). \end{aligned}$$

By the choices of $v_1$ and $v_2$, for any maximum strong attachment $\{a_1,a_2,\ldots ,a_p\}$ of $H$ to $P$ in $G^{\prime }$, there is an integer $l$, $0\le l\le p$, such that $v_1,v_2\in V(P[a_l,a_{l+1}])$, where $a_0=x$ and $a_{p+1}=z$. Since $N_H(v_1)=\{w\}=N_H(v_2)$, it follows from Lemma 1 (2) that either $N_H(a_l)$ or $N_H(a_{l+1})=\{w\}$. The former implies a strong attachment $\{a_1,\ldots ,a_l,u_j,v_2,a_{l+1},\ldots ,a_p\}$, the latter a strong attachment $\{a_1,\ldots ,a_l,v_1,u_j,a_{l+1},\ldots ,a_p\}$, of $H$ to $P$ in $G$; in either case we have that $p+2\le t$, that is, $p\le t-2=|T^{\prime }|$. This shows that $T^{\prime }$ is a maximum strong attachment of $H$ to $P$ in $G^{\prime }$, as claimed. As before, by the induction hypothesis,

$$\begin{aligned} |N_P(M)\cap T^{\prime }|\ge \min \{k-2,m+d^{\prime }_2-1\}. \end{aligned}$$

Consequently

$$\begin{aligned} |N_P(M)\cap T|\ge \min \{k-1,m+d^{\prime }_2\}, \end{aligned}$$

which completes the proof of (1).

Now we prove (2). Clearly for every vertex $u_j\in N_P(M)\cap T\backslash \{u_t\}$, the strong attached pair $\{u_j,u_{j+1}\}$ supported by $T$ is joined to $M$. If $|N_P(M)\cap T\backslash \{u_t\}|\ge \min \{k-1,m+d^{\prime }_2\}$, then the assertion is true. By (1), we assume that $|N_P(M)\cap T|=\min \{k-1,m+d^{\prime }_2\}$ and $u_t\in N_P(M)\cap T$.

By Lemma 1 (3), $t\ge \min \{k,h+d_2\}\ge \min \{k-1,m+d^{\prime }_2\}+1$. This implies that there exists at least one vertex in $T\backslash N_P(M)$. We choose a vertex $u_i\in T\backslash N_P(M)$ such that $u_{i+1}\in N_P(M)\cap T$. Then $\{u_i,u_{i+1}\}$ together with $\{u_j,u_{j+1}\}$ for $u_j\in N_P(M)\cup T\backslash \{u_t\}$ are $\min \{k-1,m+d^{\prime }_2\}$ strong attached pairs supported by $T$ joined to $M$.

Let $P,H,B,M$ be defined as in Lemma 3. In the following, we call a strong attached pair which is joined to $M$ a good pair (with respect to $M$). Let $\{u_j,u_{j+1}\}$ be a strong attached pair. If one of the vertices in $\{u_j,u_{j+1}\}$ is joined to $M$, and the other to $H-M$, then we call it a better pair (with respect to $M$); and if one of the vertices in $\{u_j,u_{j+1}\}$ is joined to $M$, and the other to $H-B$, then we call it a best pair (with respect to $M$).

3 Proof of Theorem 4

If $k=2$, then the assertion is Theorem 3. So we assume that $k\ge 3$. Since $G$ is $k$-connected and $|Y|=k-2$, $G$ contains an $(x,Y,z)$-path. In order to prove the theorem, we choose a longest $(x,Y,z)$-path $P$ in $G$. Clearly $|V(P)|\ge |Y|+2=k$. Moreover, by the $k$-connectedness of $G$, for each component $H$ of $G-P$, $H$ is locally $k$-connected to $P$, and $P$ is a locally longest $(x,Y,z)$-path with respect to $H$. So it is sufficient to prove that:

Proposition 4

Let $G$ be a graph, $P$ an $(x,Y,z)$-path of $G$, where $x,z\in V(G)$, $Y\subset V(G)$, and $|Y|=k-2$. Suppose that the average degree of vertices in $V(G)\backslash \{x,z\}$ is $r$. If for each component $H$ of $G-P$, $H$ is locally $k$-connected to $P$, and $P$ is a locally longest $(x,Y,z)$-path with respect to $H$, then $l(P)\ge r$.

Proof

We prove this proposition by induction on $|V(G-P)|$. If $V(G-P)=\emptyset$, noting that $r\le |V(G)|-1$, the result is trivially true. So we assume that $V(G-P)\ne \emptyset$. Let $H$ be a component of $G-P$.

Let $d=|N_{P}(H)|$, $\theta =|\{x,z\}\cap N_P(H)|$ and $N_P(H)=\{v_{1},v_{2},\ldots ,v_d\}$, where $v_i$, $1\le i\le d$, are in order along $P$. Then, we have

$$\begin{aligned} l(P)=l(P[x,v_{1}])+\sum _{i=1}^{d-1}l(P[v_{i},v_{i+1}])+l(P[v_d,z]). \end{aligned}$$

It is easy to know that $l(P[x,v_{1}])+l(P[v_d,z])\ge 2-\theta$ and $l(P[v_{i},v_{i+1}])\ge 2$ for $1\le i\le d-1$. Thus, we have

$$\begin{aligned} l(P)\ge 2d-\theta . \end{aligned}$$

Note that $d\ge k$ by the local $k$-connectedness of $H$ to $P$ and clearly $\theta \le 2$. If $r\le 2k-2$, then we have $l(P)\ge 2k-2\ge r$, and the proof is complete. Thus we assume that

$$\begin{aligned} r>2k-2. \end{aligned}$$

(1)

Besides, if $d\ge (r+\theta )/2$, then $l(P)\ge r$, and we complete the proof. Thus, we assume that

$$\begin{aligned} d<(r+\theta )/2. \end{aligned}$$

(2)

Let $T=\{u_1,u_2,\ldots ,u_t\}$ be a maximum strong attachment of $H$ to $P$. Set $S=N_{P}(H)\backslash T$ and $s=|S|$ (note that $s+t=d$). Let $T_r=\{u_i\in T\backslash \{u_t\}: Y\cap V(P(u_i,u_{i+1}))=\emptyset \}$ and $t_r=|T_r|$.

Clearly, for every transitive strong attached pair $\{u_j,u_{j+1}\}$, where $u_j\in T_r$, we have

$$\begin{aligned} d_{H}^{*}(u_j,u_{j+1})\ge 2. \end{aligned}$$

(3)

We distinguish two cases:

Case 1

$H$ is nonseparable.

Let $h=|V(H)|$ and $r^{\prime }$ the average degree of vertices in $V(H)$. If $r^{\prime }h+e(P-\{x,z\},H)\le rh$, then we consider the graph $G^{\prime }$ obtained from $G$ by deleting the component $H$. Note that

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{x,z\}}{d_{G^{\prime }}{(v)}}&= r(|V(G)|-2)-r^{\prime }h-e(P-\{x,z\},H)\\&\ge r(|V(G)|-2)-rh\\&=r(|V(G^{\prime })|-2). \end{aligned}$$

By the induction hypothesis, we have $l(P)\ge r$, and the proof is complete. Thus we assume that

$$\begin{aligned} r^{\prime }h+e(P-\{x,z\},H)>rh. \end{aligned}$$

(4)

We use $d_{1}$ to denote the number of vertices in $N_{P}(H)$ which have only one neighbor in $V(H)$, $d_2=d-d_1$, $\theta _{1}$ to denote the number of vertices in $\{x,z\}$ which have only one neighbor in $V(H)$ and $\theta _{2}=\theta -\theta _1$.

Clearly,

$$\begin{aligned} r^{\prime }h\le h(h-1+d_{2})+d_{1}\quad \text{ and } \quad e(P-\{x,z\},H)\le h(d_{2}-\theta _{2})+d_{1}-\theta _{1}. \end{aligned}$$

Thus, by (4), we have

$$\begin{aligned} h(h-1+2d_{2}-\theta _2)+2d_{1}-\theta _{1}\ge r^{\prime }h+e(P-\{x,z\},H)>rh. \end{aligned}$$

Note that $d_1=d-d_2$ and $\theta _1=\theta -\theta _2$, we have

$$\begin{aligned} h(h-1+2d_{2}-\theta _2)+2d-2d_2-\theta +\theta _2\ge rh. \end{aligned}$$

By (2), we have

$$\begin{aligned} h(h-1+2d_{2}-\theta _2)+(r+\theta )-2d_2-\theta +\theta _2>rh. \end{aligned}$$

Thus,

$$\begin{aligned} (h-1)(h+2d_{2}-r-\theta _{2})>0. \end{aligned}$$

This implies that $h\ge 2$ and $h+2d_{2}>r+\theta _{2}\ge r$, and then $2h+2d_2>r+2$. By (1), we have $2h+2d_2>2k$, that is

$$\begin{aligned} h+d_2>k. \end{aligned}$$

(5)

By (5) and Lemma 1 (3), $t\ge k$. Since $|Y|\le k-2$, there exists at least one transitive strong attached pair $(u_p,u_{p+1})$ supported by $T$, where $u_p\in T_r$.

Let $G^{\prime }$ be the subgraph induced by $V(H)\cup \{u_p,u_{p+1}\}$. If $u_pu_{p+1}\notin E(G)$, we add the edge $u_pu_{p+1}$ in $G^{\prime }$. Thus $G^{\prime }$ is 2-connected, and by (4),

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,u_{p+1}\}}d_{G^{\prime }}(v)&=\sum _{v\in V(H)}d(v)-e(N_P(H)\backslash \{u_p,u_{p+1}\},H)\\&=r^{\prime }h-e(N_P(H)\backslash \{u_p,u_{p+1}\},H)\\&\ge rh-e(P-\{x,z\},H)-e(N_P(H)\backslash \{u_p,u_{p+1}\},H). \end{aligned}$$

Note that

$$\begin{aligned}&e(P-\{x,z\},H)\le (s+t-\theta )h,\quad \text{ and } \\&e(N_P(H)\backslash \{u_p,u_{p+1}\},H)\le (s+t-2)h, \end{aligned}$$

we have

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,u_{p+1}\}}d_{G^{\prime }}(v)&\ge rh-(s+t-\theta )h-(s+t-2)h\\&=(r-2s-2t+\theta +2)h. \end{aligned}$$

By Theorem 3, $G^{\prime }$ contains a $(u_p,u_{p+1})$-path of length at least $r-2s-2t+\theta +2$, which implies that

$$\begin{aligned} d_{H}^{*}(u_p,u_{p+1})\ge r-2s-2t+\theta +2. \end{aligned}$$

(6)

Substituting (6) for $d_{H}^{*}(u_p,u_{p+1})$ in Lemma 2 and (3) for the other terms, we have

$$\begin{aligned} l(P)\ge (r-2s-2t+\theta +2)+2(t_{r}-1)+2(s+t-t_r)-\theta \ge r. \end{aligned}$$

Case 2

$H$ is separable.

Let $B$ be an endblock of $H$, $b$ the cut vertex of $H$ contained in $B$, $M=B-b$, $m=|V(M)|$, and $r^{\prime \prime }$ the average degree of the vertices in $V(M)$.

If $r^{\prime \prime }m+e(P-\{x,z\},M)+d_{M}(b)\le rm$, then we consider the graph $G^{\prime }$ obtained from $G$ by contracting $B$. Let $H^{\prime }$ be the component of $G^{\prime }-P$ obtained from $H$ by contracting $B$. By Proposition 3, $H^{\prime }$ is locally $k$-connected to $P$. Clearly $P$ is a locally longest $(x,Y,z)$-path with respect to $H^{\prime }$, and

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{x,z\}}d_{G^{\prime }}(v)&\ge \sum _{v\in V(G)\backslash \{x,z\}}d(v)-r^{\prime \prime }m-e(P-\{x,z\},M)-d_{M}(b)\\&\ge r(|V(G)|-2)-rm\\&=r(|V(G^{\prime })|-2). \end{aligned}$$

By the induction hypothesis, $l(P)\ge r$, and the proof is complete. Thus we assume that

$$\begin{aligned} r^{\prime \prime }m+e(P-\{x,z\},M)+d_{M}(b)>rm. \end{aligned}$$

(7)

Let $d^{\prime }_0=|N_P(H)\backslash N_P(M)|$, $d^{\prime }_1$ be the number of vertices in $N_P(M)$ which have only one neighbor in $V(H)$, $d^{\prime }_2=d-d^{\prime }_0-d^{\prime }_1$; $\theta ^{\prime }_0=|\{x,z\}\cap N_P(H)\backslash N_P(M)|$, $\theta ^{\prime }_1$ be the number of vertices in $\{x,z\}\cap N_P(M)$ which have only one neighbor in $V(H)$ and $\theta ^{\prime }_2=\theta -\theta ^{\prime }_0-\theta ^{\prime }_1$.

Now we prove that

$$\begin{aligned} m+d^{\prime }_2\ge k-1. \end{aligned}$$

(8)

Let $B^{\prime }$ be an endblock of $H$ other than $B$, $b^{\prime }$ the cut vertex of $H$ contained in $B^{\prime }$, $M^{\prime }=B^{\prime }-b^{\prime }$ and $m^{\prime }=|V(M^{\prime })|$.

By the local $k$-connectedness of $H$ to $P$, $|N_P(M^{\prime })|\ge k-1$. If $|N_P(M^{\prime })\backslash N_P(M)|\le m$, then $d^{\prime }_2\ge |N_P(M)\cap N_P(M^{\prime })|\ge k-1-m$, and $m+d^{\prime }_2\ge k-1$, and (8) holds. Thus we assume that $|N_P(M^{\prime })\backslash N_P(M)|\ge m+1$. So we have

$$\begin{aligned} d^{\prime }_0\ge m+1. \end{aligned}$$

(9)

Clearly,

$$\begin{aligned}&r^{\prime \prime }m\le m(m+d^{\prime }_2)+d^{\prime }_1,\\&e(P-\{x,z\},M)\le m(d^{\prime }_2-\theta ^{\prime }_2)+d^{\prime }_{1}-\theta ^{\prime }_1,\quad \text{ and } \\&d_M(b)\le m. \end{aligned}$$

Thus, by (7),

$$\begin{aligned} m(m+2d^{\prime }_2+1-\theta ^{\prime }_2)+2d^{\prime }_1-\theta ^{\prime }_1\ge r^{\prime \prime }m+e(P-\{x,z\},M)+d_{M}(b)>rm. \end{aligned}$$

Note that $d^{\prime }_1=d-d^{\prime }_0-d^{\prime }_2$ and $\theta ^{\prime }_1=\theta -\theta ^{\prime }_0-\theta ^{\prime }_2$, we have

$$\begin{aligned} m(m+2d^{\prime }_{2}+1-\theta ^{\prime }_2)+2d-2d^{\prime }_0-2d^{\prime }_2-\theta +\theta ^{\prime }_0+\theta ^{\prime }_2>rm. \end{aligned}$$

By (2) and (9), we have

$$\begin{aligned} m(m+2d^{\prime }_{2}+1-\theta ^{\prime }_2)+(r+\theta )-2(m+1)-2d^{\prime }_2-\theta +\theta ^{\prime }_0+\theta ^{\prime }_2>rm. \end{aligned}$$

Thus,

$$\begin{aligned} (m-1)(m+2d^{\prime }_{2}-r-\theta ^{\prime }_{2})>2-\theta ^{\prime }_0\ge 0. \end{aligned}$$

This implies that $m\ge 2$ and $m+2d^{\prime }_{2}>r+\theta ^{\prime }_{2}\ge r$, and then $2m+2d^{\prime }_2>r+2$. By (1), $2m+2d^{\prime }_2>2k$, that is $m+d^{\prime }_2>k$, and (8) holds.

By Lemma 3 (2), there exist at least $k-1$ good pairs supported by $T$ with respect to $M$. Since $|Y|=k-2$, there exists at least one transitive good pair $\{u_p,u_{p+1}\}$ with respect to $M$. Similarly there exists at least one transitive good pair $\{u_q,u_{q+1}\}$ with respect to $M^{\prime }$.

First we assume that there is a transitive best pair supported by $T$ with respect to $M$ or $M^{\prime }$. Without loss of generality, we assume that $\{u_p,u_{p+1}\}$ is a best pair, where $u_p\in N_P(M)$ and $u_{p+1}\in N_P(H-B)$. Consider the subgraph $G^{\prime }$ induced by $V(B)\cup \{u_p\}$. If $u_pb\notin E(G)$, we add the edge $u_pb$ in $G^{\prime }$. Thus $G^{\prime }$ is 2-connected, and by (7),

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,b\}}d_{G^{\prime }}(v)&=\sum _{v\in V(M)}d(v)-e(N_P(H)\backslash \{u_p\},M)\\&=r^{\prime \prime }m-e(N_P(H)\backslash \{u_p\},M)\\&\ge rm-e(P-\{x,z\},M)-d_M(b)-e(N_P(H)\backslash \{u_p\},M). \end{aligned}$$

Note that

$$\begin{aligned}&e(P-\{x,z\},M)\le (s+t-\theta )m,\\&d_M(b)\le m,\quad \text{ and } \\&e(N_P(H)\backslash \{u_p\},M)\le (s+t-1)m, \end{aligned}$$

we have

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,b\}}d_{G^{\prime }}(v)&\ge rm-(s+t-\theta )m-m-(s+t-1)m\\&=(r-2s-2t+\theta )m. \end{aligned}$$

By Theorem 3, $G^{\prime }$ contains a $(u_p,b)$-path of length at least $r-2s-2t+\theta$. It is clear that there is a $(b,u_{p+1})$-path in $H-M$ of length at least 2, which implies that

$$\begin{aligned} d_{H}^{*}(u_p,u_{p+1})\ge r-2s-2t+\theta +2. \end{aligned}$$

(10)

Substituting (10) for $d_{H}^{*}(u_p,u_{p+1})$ in Lemma 2 and (3) for the other terms, we have

$$\begin{aligned} l(P)\ge (r-2s-2t+\theta +2)+2(t_{r}-1)+2(s+t-t_r)-\theta \ge r, \end{aligned}$$

as required.

So, we assume that there are no transitive best pairs supported by $T$ with respect to $M$ or $M^{\prime }$.

Now we assume that there is a transitive better pair (but not best pair) supported by $T$ with respect to $M$ or $M^{\prime }$. Without loss of generality, we assume that $\{u_p,u_{p+1}\}$ is a better pair, where $u_p\in N_P(M)$ and $u_{p+1}\in N_P(b)$. Consider the subgraph $G^{\prime }$ induced by $V(B)\cup \{u_p\}$. If $u_pb\notin E(G)$, we add the edge $u_pb$ in $G^{\prime }$. Thus $G^{\prime }$ is 2-connected and

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,b\}}d_{G^{\prime }}(v)\ge rm-e(P-\{x,z\},M)-d_M(b)-e(N_P(H)\backslash \{u_p\},M). \end{aligned}$$

Note that

$$\begin{aligned}&e(P-\{x,z\},M)\le (s+t-\theta )m,\quad \text{ and } \\&d_M(b)\le m, \end{aligned}$$

and since at least one vertex of $u_q$ and $u_{q+1}$ is not joined to $M$ [otherwise, $\{u_q,u_{q+1}\}$ will be a best pair], we have

$$\begin{aligned} e(N_P(H)\backslash \{u_p\},M)\le (s+t-2)m. \end{aligned}$$

Thus we have

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,b\}}d_{G^{\prime }}(v)&\ge rm-(s+t-\theta )m-m-(s+t-2)m\\&=(r-2s-2t+\theta +1)m. \end{aligned}$$

By Theorem 3, $G^{\prime }$ contains a $(u_p,b)$-path of length at least $r-2s-2t+\theta +1$, and then, by $bu_{p+1}\in E(G)$,

$$\begin{aligned} d_{H}^{*}(u_p,u_{p+1})\ge r-2s-2t+\theta +2. \end{aligned}$$

Thus we also have $l(P)\ge r$.

So, we assume that there are no transitive better pairs supported by $T$ with respect to $M$ or $M^{\prime }$. Thus $\{u_p,u_{p+1}\}\cap \{u_q,u_{q+1}\}=\emptyset$, and $\{u_p,u_{p+1}\}$ and $\{u_q,u_{q+1}\}$ are two distinct strong attached pairs.

Note that $u_p$ and $u_{p+1}$ are joined to $M$ by two independent edges. Consider the subgraph $G^{\prime }$ induced by $V(B)\cup \{u_p,u_{p+1}\}$. If $u_pu_{p+1}\notin E(G)$, we add the edge $u_pu_{p+1}$ in $G^{\prime }$. Thus $G^{\prime }$ is 2-connected, and by (7),

$$\begin{aligned}&\sum _{v\in V(G^{\prime })\backslash \{u_p,u_{p+1}\}}d_{G^{\prime }}(v)\\&\quad =\sum _{v\in V(M)}d(v)-e(N_P(H)\backslash \{u_p,u_{p+1}\},M)+d_M(b)+|\{u_p,u_{p+1}\}\cap N_P(b)|\\&\quad =r^{\prime \prime }m+d_M(b)-e(N_P(H)\backslash \{u_p,u_{p+1}\},M)+|\{u_p,u_{p+1}\}\cap N_P(b)|\\&\quad \ge rm-e(P-\{x,z\},M)-e(N_P(H)\backslash \{u_p,u_{p+1}\},M). \end{aligned}$$

Note that

$$\begin{aligned}&e(P-\{x,z\},M)\le (s+t-\theta )m, \end{aligned}$$

and since neither $u_q$ and $u_{q+1}$ has neighbors in $M$ [otherwise $\{u_q,u_{q+1}\}$ will be a better pair], we have

$$\begin{aligned}&e(N_P(H)\backslash \{u_p,u_{p+1}\},M)\le (s+t-4)m. \end{aligned}$$

Thus, we have,

$$\begin{aligned} \sum _{v\in V(G^{\prime })\backslash \{u_p,u_{p+1}\}}d_{G^{\prime }}(v)&\ge rm-(s+t-\theta )m-(s+t-4)m\\&=(r-2s-2t+\theta +4)m. \end{aligned}$$

By Theorem 3, $G^{\prime }$ contains a $(u_p,u_{p+1})$-path of length at least $(r-2s-2t+\theta +4)m/({1+m})\ge (r-2s-2t+\theta +4)/2$ (note that $m\ge 1$), which implies that

$$\begin{aligned} d_{H}^{*}(u_p,u_{p+1})\ge (r-2s-2t+\theta +4)/2. \end{aligned}$$

and similarly,

$$\begin{aligned} d_{H}^{*}(u_q,u_{q+1})\ge (r-2s-2t+\theta +4)/2. \end{aligned}$$

Then,

$$\begin{aligned} d_{H}^{*}(u_p,u_{p+1})+d_{H}^{*}(u_q,u_{q+1})\ge r-2s-2t+\theta +4. \end{aligned}$$

Thus, by Lemma 2, we have

$$\begin{aligned} l(P)\ge (r-2s-2t+\theta +4)+2(t_{r}-2)+2(s+t-t_r)-\theta \ge r. \end{aligned}$$

The proof is complete.

4 Proof of Theorem 8

By the $k$-connectedness of $G$, it contains a $Y$-cycle. If $2e(G)/(n-1)\le 3$, then the result is trivially true. Thus we assume that $2e(G)/(n-1)>3$.

We choose a vertex $y\in Y$, and construct a graph $G^{\prime }$ such that $V(G^{\prime })=V(G)\cup \{y^{\prime }\}$, where $y^{\prime }\notin V(G)$ and $E(G^{\prime })=E(G)\cup \{vy^{\prime }: v\in N_{G}(y)\}$. Clearly, $G^{\prime }$ is $k$-connected. Besides, we have that

$$\begin{aligned} e(G^{\prime })=e(G)+d_{G}(y)\quad \text{ and } \quad d_{G^{\prime }}(y)=d_{G^{\prime }}(y^{\prime })=d_G(y), \end{aligned}$$

and the order of $G^{\prime }$ is $n+1$. Now, by Theorem 4, there exists a $(y,Y\backslash \{y\},y^{\prime })$-path $P$ of length at least

$$\begin{aligned} \frac{2e(G^{\prime })-d_{G^{\prime }}(y)-d_{G^{\prime }}(y^{\prime })}{(n+1)-2}=\frac{2(e(G)+d_{G}(y))-2d_{G}(y)}{n-1}=\frac{2e(G)}{n-1}. \end{aligned}$$

Let $uy^{\prime }$ be the last edge of $P$. Then $uy\in E(G)$ and $C=P[y,u]uy$ is a cycle of $G$ passing through all the vertices in $Y$ of length at least $2e(G)/(n-1)$, which completes the proof.