## Erd˝ os-Gallai Stability Theorem for Linear Forests ∗

Ming-Zhu Chen and Xiao-Dong Zhang School of Mathematical Science, MOE-LSC, SHL-MAC Shanghai Jiao Tong University, Shanghai 200240, P. R. China

## Abstract

The Erd˝ os-Gallai Theorem states that every graph of average degree more than l -2 contains a path of order l for l ≥ 2. In this paper, we obtain a stability version of the Erd˝s-Gallai Theorem in terms of minimum degree. Let o G be a connected graph of order n and F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( l i =1 P 2 b i +1 ) be k + l disjoint paths of order 2 a , . . . , 1 2 a , k 2 b 1 +1 , . . . , 2 b l +1 respectively, where , k ≥ 0, 0 ≤ l ≤ 2, and k + l ≥ 2. If the minimum degree δ G ( ) ≥ ∑ k i =1 a i + ∑ l i =1 b i -1, then F ⊆ G except several classes of graphs for sufficiently large n , which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.

AMS Classification: 05C35, 05C05

Key words: Erd˝ os-Gallai Theorem; Stable problem; Linear forest; Path.

## 1 Introduction

## 1.1 Notation

Let G be a finite simple undirected graph with vertex set V ( G ) and edge set E G ( ). Denote e G ( ) by the number of edges of G . For v ∈ V ( G ), the neighborhood N G ( v ) of v is { u : uv ∈ E G ( ) } and the degree d G ( v ) of v is | N G ( v ) . | For a subgraph H of G , the H -neighborhood N H ( v ) of v is N G ( v ) ⋂ V ( H ) and the H -degree d H ( v ) of v is | N H ( v ) . | Denote δ G ( ) by minimum degree of G . Denote P n , K n , and K m,n by a path of order n , a complete graph of order n , and a complete bipartite graph with partition of size m and n , respectively. For two disjoint graphs G and H , denote G ⋃ H and G ∨ H by the disjoint union of G and H , and the join of G and H which is obtained from G ⋃ H by joining every vertex of G to every vertex of H , respectively. Moreover, kG denotes a graph consisting of k disjoint copies of G and G denotes the complement of G . For X ⊆ V ( G ), G X [ ] denotes the graph induced by X and write E X ( ) for E G X ( [ ]). For X,Y ⊆ V ( G ), e X, Y ( ) denotes the number of the edges of G with one end vertex in X and the other in Y . For two graphs G and H , write H ⊆ G if G contains H as a subgraph, and H /notsubseteql G otherwise. An odd (even) path is a path of odd (even) order. A graph is connected if there is a path

∗ This work is supported by the Joint NSFC-ISF Research Program (jointly funded by the National Natural Science Foundation of China and the Israel Science Foundation (No. 11561141001)), the National Natural Science Foundation of China (Nos.11531001 and 11271256), Innovation Program of Shanghai Municipal Education Commission (No. 14ZZ016) and Specialized Research Fund for the Doctoral Program of Higher Education (No.20130073110075).

† Corresponding author: Xiao-Dong Zhang (Email: xiaodong@sjtu.edu.cn),

between every pair of vertices. A connected graph G is k -connected if | V ( G ) | &gt; k and G -X is connected for every set X ⊆ V ( G ) with | X &lt; k | . A graph G is F -free if it does not contain F as a subgraph. A star forest is a forest whose components are stars and a linear forest is a forest whose components are paths. A cut vertex (edge) of a graph G is a vertex (edge) whose removal increases the number of components of G . A block of is a maximal connected subgraph without any cut vertex. An end block of G is block that contains precisely a cut vertex of G . For two end blocks B 1 and B 2 of a graph G , denote p B , B ( 1 2 ) by the order of a longest path between the unique cut vertex of G in V ( B 1 ) and the unique cut vertex of G in V ( B 2 ). For other notations not defined here, readers are referred to [10].

## 1.2 History and known results

The study of Tur´n-type problems is the center of extremal graph theory. a Erd˝ os and Gallai in [6] proved the following key result, which opens a new subject for degenerate graphs:

Theorem 1.1. [6] Let G be a graph of order n . If e G ( ) &gt; ( l -2) n 2 , where l ≥ 2 , then P l ⊆ G .

Let H n,l,a := K a ∨ ( K l -2 a ⋃ K n -l + a ) with h n, l, a ( ) := e H ( n,l,a ) = ( l -a 2 ) + ( a n -l + a ) for a ≤ /floorleft l 2 /floorright . Recently, F¨ uredi, Kostochka, and Verstra¨te e [7] obtained a stability theorem for paths.

Theorem 1.2. [7] Let G be a connected graph of order n , where t ≥ 2 and n ≥ 3 t -1 . If e G ( ) &gt; h n ( +1 , l +1 , t -1) -n , where l ∈ { 2 t, 2 t +1 } , then P l ⊆ G , unless one of following holds:

/negationslash

(i). l = 2 t , l = 6 , and G ⊆ H n,l,t -1 ;

(ii). l = 2 t +1 or l = 6 , and G -A is a star forest for some A ⊆ V ( G ) of size at most l -1 .

Another question in Tur´n-type problems which has received extensive attention a is how large minimum degree of a graph G is to guarantee P l ⊆ G . Erd˝ os and Gallai [6] and Andrasfai [1] proved the following result for an odd path.

Theorem 1.3. [6, 1] Let G be a connected graph of order n , where n ≥ 2 h +3 ≥ 3 . If δ G ( ) ≥ h +1 , then P 2 h +3 ⊆ G .

Let S n,h := K h ∨ K n -h and S + n,h be a graph obtained by adding an edge to S n,h , i.e., S + n,h = K h ∨ ( K 2 ⋃ K n - -h 2 ) (see Fig.1).

Fig.1. Graphs S n,h and S + n,h .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00665v1-figure-23a4c653-329b-4fcf-a4d3-ab935decd854.jpg)

Given t 1 , t 2 ≥ 0, let L t 1 ,t 2 ,h,h +1 := K 1 ∨ ( t 1 K h ⋃ t 2 K h +1 ) (see Fig.2). In particular, write L t, 0 ,h,h +1 := L t,h (see Fig.2). The center of L t 1 ,t 2 ,h,h +1 is the vertex of maximum degree in L t 1 ,t 2 ,h,h +1 .

Fig.2. Graphs L t 1 ,t 2 ,h,h +1 and L t,h .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00665v1-figure-2d0941b6-5f26-4522-8490-d23369a59877.jpg)

For an even path, the question was answered by Ali and Staton [2].

Theorem 1.4. [2] Let G be a connected graph of order n , where n ≥ 2 h + 2 . If δ G ( ) ≥ h ≥ 1 , then P 2 h +2 ⊆ G unless either G ⊆ S n,h or G = L t,h , where n = th +1 .

Recently, Yuan and Nikiforov [9] gave a stability version of Theorem 1.3.

Theorem 1.5. [9] Let G be a connected graph of order n , where n ≥ 2 h + 3 . If δ G ( ) ≥ h ≥ 2 , then P 2 h +3 ⊆ G , unless unless one of following holds:

- (i). G ⊆ S + n,h ;
- (ii). G = L t,h , where n = th +1 ;
- (iii). G ⊆ L t,h, 1 ,h +1 , where n = ( t +1) h +2 ;

(iv). G is obtained by joining the centers of two disjoint graphs L s,h and L t,h , where n = ( s + ) t h +2 .

Bushaw and Kettle [3] proved the maximum number of edges in a kP l -free graph of sufficiently large order n for l ≥ 3 and determined all the extremal graphs. Recently, Yuan and Zhang [11] extended their result for l = 3 and all possible n and k . Lidick´, y Liu, and Palmer [8] extended Bushaw-Kettle result for linear forests. Their main result can be stated as follows.

Theorem 1.6. [8] Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( l i =1 P 2 b i +1 ) and h = k ∑ i =1 a i + l ∑ i =1 b i -1 , where k + l ≥ 2 , a 1 ≥ · · · ≥ a k ≥ 1 , and b i ≥ 1 for 1 ≤ i ≤ l . Let G be an F -free graph of sufficiently large order n . (i). If k ≥ 1 , then e G ( ) ≤ e S ( n,h ) with equality if and only if G = S n,h ; (ii). If k = 0 and there is at least one b i such that b i &gt; 1 , where 1 ≤ i ≤ l , then e G ( ) ≤ e S ( + n,h ) with equality if and only if G = S + n,h .

It is easy to see that we have the following result from Theorem 1.6.

Corollary 1.7. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( l i =1 P 2 b i +1 ) and h = k ∑ i =1 a i + l ∑ i =1 b i -1 , where k + l ≥ 2 , a 1 ≥ · · · ≥ a k ≥ 1 , and b i ≥ 1 for 1 ≤ i ≤ l . Let G be a graph of

(ii). If k = 0 , δ &gt; 2 h -n , and there is at least one b i such that b i &gt; 1 , where sufficiently large order n . (i). If k ≥ 1 and δ &gt; 2 h -h 2 + h n , then F ⊆ G ; h 2 + h -4 1 ≤ i ≤ l , then F ⊆ G .

The related results can be referred to [4] and references therein.

## 1.3 Our main results

In this paper, we obtain stability versions of Corollary 1.7 for a graph which does not contain a linear forest with at most two odd paths. The main results in this paper are Theorems 1.8-1.11.

Theorem 1.8. Let F = ⋃ k i =1 P 2 a i and h = ∑ k i =1 a i -1 ≥ 1 , where k ≥ 2 and a 1 ≥ · · · ≥ a k ≥ 1 . Let G be a connected graph of order n , where n ≥ 2 h + 2 . If δ G ( ) ≥ h , then F ⊆ G , unless one of the following holds:

- (i). G ⊆ S n,h ;
- (ii). F = 2 P 2 a 1 and G = L t,h , where n = th +1 .

Remark 1. The minimum degree condition is best possible. For example, let F = 2 P 2 a 1 and h = 2 a 1 -1. If G = L n -1 h -1 ,h -1 , where n = h h ( -1) q +1 with positive integer q , then δ G ( ) = h -1, F /notsubseteql G G , /notsubseteql S n,h , and G /notapproxequal L n -1 h ,h . So Theorem 1.8 does not hold for δ G ( ) = h -1. For another example, let F = P 2 ⋃ 2 P 4 and h = 4. If G = L n -1 3 , 3 where n = 12 q +1 with positive integer q , then δ G ( ) = 3, F /notsubseteql G , and G /notsubseteql S n, 4 . So Theorem 1.8 does not hold for δ G ( ) = h -1. Therefore the condition δ G ( ) ≥ h in Theorem 1.8 can not be weaken and is best possible.

Theorem 1.9. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ P 2 b 1 +1 and h = ∑ k i =1 a i + b 1 -1 ≥ 1 , where k ≥ 1 , a 1 ≥ · · · ≥ a k ≥ 1 , and b 1 ≥ 1 . Let G be a connected graph of order n , where n ≥ 2 h +3 . If δ G ( ) ≥ h , then F ⊆ G , unless one of the following holds:

- (i). G ⊆ S n,h ;
- (iii). F ∈ { P 2 b 1 ⋃ P 2 b 1 +1 , P 2 b 1 +2 ⋃ P 2 b 1 +1 } and G = L t,h , where n = th +1 .
- (ii). F = P 6 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 , where n is even;

Remark 2 . The minimum degree condition is best possible. For example, let F = P 2 b 1 ⋃ P 2 b 1 +1 and h = 2 b 1 . If G = L n -1 h -1 ,h -1 , where n = h h ( -1) q + 1 with positive integer q , then δ G ( ) = h -1, F /notsubseteql G G , /notsubseteql S n,h , and G /notapproxequal L n -1 h ,h . Thus Theorem 1.9 does not hold for δ G ( ) = h -1. For another example, let F = P 4 ⋃ P 2 ⋃ P 3 and h = 3. If G = L n -1 2 , 2 , where n = 6 q +1 with positive integer q , then δ G ( ) = 2, F /notsubseteql G , and G /notsubseteql S n, 3 . Thus Theorem 1.9 does not hold for δ G ( ) = h -1. Therefore the condition δ G ( ) ≥ h in Theorem 1.9 is necessary and best possible.

Theorem 1.10. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 ≥ 2 , and G be a 2-connected graph of order n , where k ≥ 0 , a 1 ≥ · · · ≥ a k ≥ 1 , b 1 ≥ b 2 , and n ≥ 4(2 h +1) 2 ( 2 h +1 h ) .

- (i). G ⊆ S n,h ;
- (a). If δ G ( ) ≥ h and k = 0 , then F ⊆ G , unless one of the following holds: +
- (ii). F = P 7 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 , where n is even;
- (iii). F = P 9 ⋃ P 3 and G ⊆ K 3 ∨ n -3 2 K 2 , where n is odd.

(b). If δ G ( ) ≥ h and k ≥ 1 , then F ⊆ G , unless one of the following holds: (iv). G ⊆ S n,h ;

(v). F = P 4 ⋃ 2 P 3 and G ⊆ K 2 ∨ n - 2 2 K 2 , where n is even;

(vi). F = P 6 ⋃ 2 P 3 and G ⊆ K 3 ∨ n - 3 2 K 2 , where n is odd.

Let H 1 n be a graph of order n , where n ≥ 7, obtained from S n, 2 and K 3 by identifying a vertex with maximum degree of S n, 2 with a vertex of K 3 (see Fig.3). Let H 2 n be a graph order n , where n ≥ 9, obtained from H 1 n -2 and K 3 by identifying a vertex with the second largest degree of H 1 n -2 with a vertex of K 3 (see Fig.3).

Let U 3 ,h be a graph of order 3 h +3 obtained from 3 K h +1 and K 3 by identifying every vertex of K 3 with a vertex of K h +1 , respectively (see Fig.3).

Fig.3. Graphs H 1 n , H 2 n , and U 3 ,h .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00665v1-figure-431d9bdb-c3e9-45e4-a7e8-029f1a49fc59.jpg)

For h ≥ 2, let F t 1 ,t 2 ,h,h +1 be a graph of order t 1 h +( t 2 +1)( h +1) + 1 obtained from L t 1 ,t 2 ,h,h +1 and K h +1 by adding an edge joining the center of L t 1 ,t 2 ,h,h +1 and a vertex of K h +1 (see Fig.4). Moreover, for h ≥ 2, let T t 1 ,t 2 ,h,h +1 be a graph of order t 1 h + ( t 2 + 2)( h + 1) + 1 obtained from L t 1 ,t 2 ,h,h +1 and 2 K h +1 by adding an edge joining the center of L t 1 ,t 2 ,h,h +1 and a vertex of each K h +1 , respectively (see Fig.4).

Fig.4. F t 1 ,t 2 ,h,h +1 and T t 1 ,t 2 ,h,h +1 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00665v1-figure-7daf5088-72e1-4379-8b11-1c2e7fbcc04f.jpg)

Theorem 1.11. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 , and G be a connected graph of order n with at least one cut vertex, where k ≥ 0 , a 1 ≥ · · · ≥ a k ≥ 1 , b 1 ≥ b 2 ≥ 1 , and n ≥ 2 h +4 .

(a). If δ G ( ) ≥ h ≥ 1 and k = 0 , then F ⊆ G , unless one of the following holds: (i) F = P 5 ⋃ P 3 and either G ⊆ H 1 n or G ⊆ H 2 n ;

(iii) F = 2 P 2 b 1 +1 and G = U 3 ,h , where n = 3 h +3 ;

(ii) F = P 2 b 1 +1 ⋃ P 2 b 1 -1 and G = L t,h , where n = th +1 ;

- (iv) F = 2 P 2 b 1 +1 and G ⊆ L t 1 ,t 2 ,h,h +1 , where n = t 1 h + t 2 ( h +1) + 1 (v) F = 2 P 2 b 1 +1 and G ⊆ F t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +1)( h +1) + 1 (vi) F = 2 P 2 b 1 +1 and G ⊆ T t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +2)( h +1) + 1 .
- (b). If δ G ( ) ≥ h ≥ 2 an k ≥ 1 , then F ⊆ G , unless F = P 2 ⋃ 2 P 2 b 1 +1 and G = L t,h , where n = th +1 .

The rest of this paper is organized as follows. In Section 2, some technical lemmas are provided. In Section 3, we present the proofs of Theorems 1.8 and 1.9. In Section 4, we present the proofs of Theorems 1.10 and 1.11.

## 2 Preliminary

In order to prove Theorems 1.8-1.11, we require several known and new technical lemmas.

Lemma 2.1. [6] Let G be a 2-connected graph of order n with u 1 ∈ V ( G ) . If d u ( ) ≥ h ≥ 2 for any vertex u different from u 1 , then there is a path P min { n, 2 h } with end vertex u 1 and P min { n, 2 h } ⊆ G .

Lemma 2.2. [5] Let G be a 2-connected graph of order at least 2 h , where h ≥ 2 . If δ G ( ) ≥ h , then C l ⊆ G , where l ≥ 2 h .

Lemma 2.3. [8] Let G be a graph of order n with a set P of p vertices, where p ≥ 2 and n ≥ 4 p 2 ( p /floorleft p 2 /floorright ) . If e P, V ( ( G ) \ P ) ≥ /floorleft ( p 2 /floorright -1 2 ) n , then P contains a subset of /floorleft p 2 /floorright vertices with a common neighborhood of p vertices in V ( G ) \ P .

Lemma 2.4. Let G be a connected graph of order n with a longest cycle C l and δ G ( ) ≥ h ≥ 2 . Let U = V ( G ) \ V ( C l ) .

- (i). If l = 2 h and U is an independent set, then G ⊆ S n,h .
- (ii). If l = 2 h +1 and P 2 h +3 /notsubseteql G , then G ⊆ S + n,h .
- (iii). If l = 2 h + 2 and P 2 h +4 /notsubseteql G , then N C l ( u 1 ) = N C l ( u 2 ) and h ≤ d C l ( u 1 ) = d C l ( u 2 ) ≤ h +1 for every pair of vertices u , u 1 2 ∈ U .

Proof. Let C l = v v 1 2 · · · v v l 1 . Since C l is a longest cycle, none of vertices in U is adjacent to any two consecutive vertices of C l .

- ( ). i Since l = 2 h and U is an independent set, d C l ( u ) = h for all u ∈ U . Furthermore either N C l ( u ) = { v , v 1 3 , . . . , v 2 h -1 } or N C l ( u ) = { v , v 2 4 , . . . , v 2 h } for all u ∈ U . In fact, if there exist two distinct vertices u , u ∈ U such that N ( u ) =
- 1 2 C l 1 { v , v 1 3 , . . . , v 2 h -1 } and N C l ( u 2 ) = { v , v 2 4 , . . . , v 2 h } , then a cycle u v v 1 1 2 h u v v v 2 2 3 4 · · · v 2 h -3 v 2 h -2 v 2 h -1 u 1 is a longer cycle than C l , a contradiction. Hence, we assume without loss of generality that N C l ( u ) = { v , v 2 4 , . . . , v 2 h } for all u ∈ U . Moreover, { v , v 1 3 , . . . , v 2 h -1 } is an independent set. In fact, if there exists an edge v 2 +1 s v 2 +1 t ∈ E G ( ) with 1 ≤ 2 s +1 &lt; 2 +1 t ≤ 2 h -1, then a cycle uv 2 t v 2 t -1 v 2 t -2 · · · v 2 +2 s v 2 +1 s v 2 +1 t v 2 +2 t · · · v 2 h -1 v 2 h v v 1 2 · · · v 2 s -1 v 2 s u for u ∈ U is a longer cycle than C l , a contradiction. Hence G ⊆ S n,h .

( ii ). If l = 2 h +1 and P 2 h +3 /notsubseteql G , then U is an independent set and d C l ( u ) = h for all u ∈ U . Furthermore, we claim that N C l ( u 1 ) = N C l ( u 2 ) for any two vertices u , u 1 2 ∈ U . In fact, we suppose without loss of generality that there exists v ∈ N C l ( u 2 ) \ N C l ( u 1 ). Since P 2 h +3 /notsubseteql G , neither of two neighbors of v along C l belongs to N C l ( u 1 ). Hence N C l ( u 1 ) is a subset of a set consisting of 2 h -2 consecutive vertices of C l . Furthermore, since C l is a longest cycle, u 1 is not adjacent to any two consecutive vertices of C l . Hence we d C l ( u 1 ) ≤ h -1, a contradiction. We

assume without loss of generality that N C l ( u ) = { v , v 2 4 , . . . , v 2 h } for all u ∈ U . Moreover, { v , v 1 3 , . . . , v 2 h -1 } is an independent set. Otherwise there exists an edge v 2 +1 s v 2 +1 t ∈ E G ( ) with 1 ≤ 2 s + 1 &lt; 2 t + 1 ≤ 2 h -1, which causes a longer cycle uv 2 t v 2 t -1 v 2 t -2 · · · v 2 +2 s v 2 +1 s v 2 +1 t v 2 +2 t · · · v 2 h v 2 h +1 v 1 · · · v 2 s u for u ∈ U than C l , a contradiction. Similarly, { v , . . . , v 3 2 h +1 } is also an independent set. Hence G U [ ⋃ { v , . . . , v 1 2 h +1 } ] contains at most one edge v v 1 2 h +1 . Therefore G ⊆ S + n,h .

( iii ) . If l = 2 h + 2 and P 2 h +4 /notsubseteql G , then U is an independent set and h ≤ d C l ( u ) ≤ h +1 for all u ∈ U . Furthermore, N C l ( u 1 ) = N C l ( u 2 ) for any two vertices u , u 1 2 ∈ U . In fact, suppose without loss of generality that there exists a vertex v ∈ N C l ( u 2 ) \ N C l ( u 1 ). Since P 2 h +4 /notsubseteql G , neither of two neighbors of v along C l belongs to N C l ( u 1 ). Hence N C l ( u 1 ) is a subset of a set consisting of 2 h -1 consecutive vertices of C l . Furthermore, since C l is a longest cycle, u 1 is not adjacent to any two consecutive vertices of C l . Hence d C l ( u 1 ) ≤ h -1, a contradiction. Hence N C l ( u 1 ) = N C l ( u 2 ) and the assertion holds. /square

Lemma 2.5. Let G be a connected graph of order n with a longest cycle C l and minimum degree δ G ( ) , where l ≤ 2 h +1 and δ G ( ) ≥ h ≥ 2 . Let U = V ( G ) \ V ( C l ) . (i). If G U [ ] is P 3 -free, then N C l ( u 1 ) = N C l ( u 2 ) for every edge u u 1 2 ∈ E U ( ) . (ii). If G U [ ] is P 4 -free, then N C l ( u 1 ) = N C l ( u 3 ) for every P 3 = u u u 1 2 3 ⊆ G U [ ] .

- Proof. ( ). i Suppose that there exists a vertex v ∈ N C l ( u 2 ) \ N C l ( u 1 ) for some edge u u 1 2 ∈ E U ( ). Since C l is a longest cycle, the distance along C l between v and any vertex in N C l ( u 1 ) is at least 3. Thus N C l ( u 1 ) is a subset of a set consisting of at most 2 h -5 consecutive vertices of C l . Furthermore, since C l is a longest cycle, u 1 is not adjacent to any two consecutive vertices of C l . These discussions imply that d C l ( u 1 ) ≤ h -2. However, since P 3 /notsubseteql G U [ ], we have d C l ( u 1 ) ≥ d G ( u 1 ) -1 ≥ h -1, a contradiction. Hence the assertion holds.
- ( ii ). Suppose that there exists a vertex v ∈ N C l ( u 3 ) \ N C l ( u 1 ) for some path P 3 = u u u 1 2 3 ⊆ G U [ ]. Since C l is a longest cycle, the distance along C l between v and any vertex in N C l ( u 1 ) is at least 4. Hence N C l ( u 1 ) is a subset of a set consisting of at most 2 h -7 consecutive vertices of C l . Furthermore, since C l is a longest cycle, u 1 is not adjacent to any two consecutive vertices of C l . These discussions imply that d C l ( u 1 ) ≤ h -3. However, since P 4 /notsubseteql G U [ ], we have d C l ( u 1 ) ≥ d G ( u 1 ) -2 ≥ h -2, a contradiction. Hence the assertion holds. /square

Lemma 2.6. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) and h = ∑ k i =1 a i + ∑ 2 i =1 b i - ≥ 1 2 , where k ≥ 0 , a 1 ≥ · · · ≥ a k ≥ 1 , and b 1 ≥ b 2 ≥ 1 . Let H , i.e., H = ( X,Y ; E ) , be a complete bipartite graph with partition size | X | = h and | Y | = h +2 .

- ( ) i . If k ≥ 1 and the graph G is obtained from H and P 3 by identifying a vertex u ∈ X with an end vertex of P 3 , then F ⊆ G .
- ( ii ) . If the graph G is obtained from H and P 4 by identifying a vertex u ∈ X with an end vertex of P 4 , then F ⊆ G .
- ( iii ) . If the graph G is obtained from H -v with v ∈ X and P 6 by identifying u ∈ X with an end vertex of P 6 , then F ⊆ G .

Proof. ( ) i . Since H is a complete bipartite graph with partition size | X | = h and | Y | = h + 2, there exist three disjoint complete bipartite subgraphs H i of H , i.e., H i = ( X , Y i i : E i ) for 1 ≤ i ≤ 3, where | X 1 | = | Y 1 | = ∑ k i =1 a i -1 with u ∈ X 1 ,

| X 2 | = b 1 , | Y 2 | = b 1 + 1, | X 3 | = b 2 , and | Y 3 | = b 2 + 1. Hence there exists a path P ∑ k i =1 2 a i -2 in H 1 with one end vertex u . In addition, there exist two disjoint paths P 2 b 1 +1 in H 2 and P 2 b 2 +1 in H 3 . Hence F ⊆ G . So ( ) holds. i By a similar argument in ( ) i , it is easy to see that ( ii ) and ( iii ) hold. /square

Lemma 2.7. Let H be a 2-connected graph of order n , where n ≥ 2 h + 1 and 2 ≤ h ≤ 3 , and u 1 ∈ V ( H ) such that d H ( u ) ≥ h for every u different from u 1 . Let G be a graph obtained from H and P t by identifying u 1 with an end vertex of P t , where 3 ≤ t ≤ 4 .

- ( ) i . If h = 2 and t = 3 , then 2 P 2 ⋃ P 3 ⊆ G P , 4 ⋃ P 3 ⊆ G , and P 2 ⋃ P 5 ⊆ G . ( ii ) . If h = 2 and t = 4 , then P P ⊆ G .

5 ⋃ 3 ( iii ) . If h = 3 and t = 4 , then P 7 ⋃ P 3 ⊆ G and 2 P 5 ⊆ G .

Proof. ( ). i Let C l be a longest cycle in H . Since H be a 2-connected graph, δ H ( ) ≥ 2. By Lemma 2.2, l ≥ 4. Since H is connected, if l ≥ 5 then 2 P 2 ⋃ P 3 ⊆ G , P 4 ⋃ P 3 ⊆ G , and P 2 ⋃ P 5 ⊆ G . Since n ≥ 5, if l = 4 then there exists a vertex v ∈ V ( H ) \ V ( C l ) adjacent to some vertex of C l . We have 2 P 2 ⋃ P 3 ⊆ G P , 4 ⋃ P 3 ⊆ G , and P 2 ⋃ P 5 ⊆ G . Thus the assertion holds.

- ( ii ). The proof of ( ii ) is similar to that of ( ) and the detail is omitted. i

( iii ). By Lemma 2.1, H has a path P 6 with an end vertex u 1 . Let P 6 = u u 1 2 · · · u 6 . Since n ≥ 7, there exists a vertex v ∈ V ( H ) \ V ( P 6 ) adjacent to some vertex of P 6 . If u 1 , u 3 , or u 6 ∈ N P 6 ( v ), then P 7 ⋃ P 3 ⊆ G and 2 P 5 ⊆ G . Furthermore, if { u , u 4 5 } ⊆ N P 6 ( v ), then P 7 ⋃ P 3 ⊆ G and 2 P 5 ⊆ G . Next we assume N P 6 ( v ) ∈ {{ v , v 2 4 } { , v , v 2 5 } { , u 2 } { , u 4 } { , u 5 }} . Since d H ( v ) ≥ 3, if N P 6 ( v ) ∈ {{ v , v 2 4 } { , v , v 2 5 }} then there exists a vertex in V ( H ) \ V ( P 6 ) adjacent to v . Thus P 7 ⋃ P 3 ⊆ G and 2 P 5 ⊆ G . Moreover, since d H ( v ) ≥ 3, if N P 6 ( v ) ∈ {{ u 4 } { , u 5 }} then there exists two distinct vertices in V ( H ) \ V ( P 6 ) adjacent to v . Thus P 7 ⋃ P 3 ⊆ G and 2 P 5 ⊆ G . Finally, since H is 2-connected, if N P 6 ( v ) = { u 2 } then there exists a vertex in V ( H ) \ V ( P 6 ) adjacent to some vertex in V ( P 6 ) \{ u 2 } ( { u 2 } can not separate V ( P ) \{ u 2 } from the rest). By repeating the arguments above, P 7 ⋃ P 3 ⊆ G and 2 P 5 ⊆ G . Thus the assertion holds. /square

Lemma 2.8. Let H be a 2-connected graph of order n and H /notsubseteql S n, 2 , where n ≥ 6 . If a graph G is obtained from H and P 3 by identifying a vertex u 1 ∈ V ( H ) with an end vertex of P 3 , then P 5 ⋃ P 3 ⊆ G .

Proof. Suppose P 5 ⋃ P 3 /notsubseteql G . Let C l be a longest cycle in H . Since H is 2connected, δ H ( ) ≥ 2. By Lemma 2.2, l ≥ 4.

Case 1 : l ≥ 6, or l = 5 with u 1 / V ∈ ( C l ). According to the structure of G , we have P 5 ⋃ P 3 ⊆ G , a contradiction.

Case 3: l = 4. There exists a shortest path P k between u 1 and some vertex of C l such that | V ( P k ) ⋂ V ( C l ) | = 1. Since P 5 ⋃ P 3 /notsubseteql G , we have 1 ≤ k ≤ 2.

Case 2 : l = 5 with u 1 ∈ V ( C l ). Since n ≥ 6, there exists a vertex u ∈ V ( H ) \ V ( C l ) adjacent to some vertex of C l . Furthermore, since P 5 ⋃ P 3 /notsubseteql G , we have N C l ( u ) = { u 1 } . Moreover, since δ H ( ) ≥ 2, there exists a vertex in V ( H ) \ V ( C l ) adjacent to u . Hence P 5 ⋃ P 3 ⊆ G , a contradiction.

/negationslash

Subcase 3.1: k = 2. Let C 4 = v v v v v 1 2 3 4 1 , V ( C 4 ) ⋂ V ( P 2 ) = { v 1 } , and U = V ( H ) \ ( V ( C 4 ) ⋃ { u 1 } ). It is easy to see that U = ∅ . First we assume that U is

an independent set. Since C 4 is a longest cycle in H and δ H ( ) ≥ 2, N H ( u ) ∈ {{ u , v 1 1 } { , v , v 1 3 } { , v , v 2 4 }} for every u ∈ U . However, in each case, P 5 ⋃ P 3 ⊆ G , a contradiction. Next we assume that H U [ ] contains at least one edge. Then there exists one edge w w 1 2 such that one of w 1 and w 2 is adjacent to some vertex in V ( C 4 ) ⋃ { u 1 } and therefore P 5 ⋃ P 3 ⊆ G , a contradiction.

Subcase 3.2 : k = 1. Obviously u 1 ∈ V ( C 4 ). Let C 4 = u u u u u 1 2 3 4 1 and U = V ( H ) \ V ( C 4 ). Since n ≥ 6, we have | U | ≥ 2. First we assume that U is an independent set. Since C 4 is a longest cycle and δ H ( ) ≥ 2, either N H ( v ) = { u , u 1 3 } or N H ( v ) = { u , u 2 4 } for v ∈ U . We claim that N H ( v ) = { u , u 1 3 } for all v ∈ U . Otherwise P 5 ⋃ P 3 ⊆ G , a contradiction. Moreover, since P 5 ⋃ P 3 /notsubseteql G , it follows that u u 2 4 / E G ∈ ( ). Hence H ⊆ S n, 2 , a contradiction. Next we assume that H U [ ] contains at least one edge v v 1 2 . Furthermore, since P 5 ⋃ P 3 /notsubseteql G , we have P 3 /notsubseteql H U [ ]. By Lemma 2.5 (i), N C 4 ( v 1 ) = N C 4 ( v 2 ). Since C 4 is a longest cycle, d C 4 ( v 1 ) = d C 4 ( v 2 ) = 1. This discussion implies that the unique common neighbor of v 1 and v 2 in V ( C 4 ) is a cut vertex of H , which contradicts that H is 2-connected.

Thus the assertion holds. /square

## 3 Proofs of Theorems 1.8 and 1.9

Now we are ready to prove Theorem 1.8, i.e.,

Theorem 3.1. Let F = ⋃ k i =1 P 2 a i and h = ∑ k i =1 a i -1 ≥ 1 , where k ≥ 2 and a 1 ≥ · · · ≥ a k ≥ 1 . Let G be a connected graph of order n , where n ≥ 2 h + 2 . If δ G ( ) ≥ h , then F ⊆ G , unless one of the following holds:

- (i). G ⊆ S n,h ;

(ii). F = 2 P 2 a 1 and G = L t,h , where n = th +1 .

Proof. Suppose F /notsubseteql G . Since ∑ k i =1 2 a i = 2 h +2, we have P 2 h +2 /notsubseteql G . We consider the following two cases.

Case 1: G is 2-connected. It follows that δ G ( ) ≥ 2. Let C l be a longest cycle in G and U = V ( G ) \ V ( C l ). By Lemma 2.2, l ≥ 4. First we claim that h ≥ 2. In fact, if h = 1, then F = 2 P 2 and thus F ⊆ G , a contradiction. By Lemma 2.2, h ≥ 2 and therefore l ≥ 2 h . Since n ≥ 2 h + 2 and P 2 h +2 /notsubseteql G , we have l ≤ 2 h and therefore l = 2 h . Moreover, since P 2 h +2 /notsubseteql G U , is an independent set. By Lemma 2.4 ( ), i G ⊆ S n,h .

Case 2: G has at least one cut vertex. Since k ≥ 2, if h = 1 then F = 2 P 2 . Since F /notsubseteql G G , must be a star K 1 ,n -1 , i.e., G = L n -1 1 , . Next we assume that h ≥ 2. Since G has at least one cut vertex, there exist at least two end blocks. We claim that | V ( B ) | = h + 1 for every end block B of G . In fact, since δ G ( ) ≥ h , it follows that | V ( B ) | ≥ h +1. Furthermore, since P 2 h +2 /notsubseteql G , Lemma 2.1 implies that B has order at most h +1 and hence | V ( B ) | = h +1. Let B i be an end block of G with a vertex u i which is a cut vertex of G for 1 ≤ i ≤ 2. It follows that | V ( B i ) | = h +1 for 1 ≤ i ≤ 2. If there exists a path P k with k ≥ 2 starting at u 1 and ending at u 2 such that V ( P k ) ⋂ ( V ( B 1 ) ⋃ V ( B 2 )) = { u , u 1 2 } , then Lemma 2.1 implies P 2 h +2 ⊆ G , a contradiction. It follows that G = L t,h , where n = th + 1. Moreover, since n ≥ 2 h +2, G has at least three blocks, i.e., t ≥ 3. By Lemma 2.1,

P h ⋃ P 2 h +1 ⊆ G . We claim that k = 2 and a 1 = a 2 . Otherwise, since

$$h = \sum _ { i = 1 } ^ { k } a _ { i } - 1 \geq 2 a _ { k }$$

and

$$2 h + 1 = \sum _ { i = 1 } ^ { k } 2 a _ { i } - 1 \geq \sum _ { i = 1 } ^ { k - 1 } 2 a _ { i },$$

we have F ⊆ G , a contradiction. Therefore F = 2 P 2 a 1 and G = L t,h , where n = th +1. /square

Theorem 1.9 can be stated as follows.

Theorem 3.2. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ P 2 b 1 +1 and h = ∑ k i =1 a i + b 1 -1 ≥ 1 , where k ≥ 1 , a 1 ≥ · · · ≥ a k ≥ 1 , and b 1 ≥ 1 . Let G be a connected graph of order n , where n ≥ 2 h +3 . If δ G ( ) ≥ h , then F ⊆ G , unless one of the following holds:

(i).

G

⊆

S

;

n -2

n,h

.

(ii). F = P 6 ⋃ P 3 and G ⊆ K 2 ∨ 2 K 2 , where n is even; (iii). F ∈ { P 2 b 1 ⋃ P 2 b 1 +1 , P 2 b 1 +2 ⋃ P 2 b 1 +1 } and G = L t,h , where n = th +1

Proof. Suppose F /notsubseteql G . Since ∑ k i =1 2 a i +2 b 1 +1 = 2 h +3, we have P 2 h +3 /notsubseteql G . We consider the following two cases.

Case 1: G is 2-connected. It follows that δ G ( ) ≥ 2. Let C l , denoted by v v 1 2 · · · v v l 1 , be a longest cycle in G and U = V ( G ) \ V ( C l ). By Lemma 2.2, l ≥ 4. We claim that h ≥ 2. In fact, if h = 1, then F = P 2 ⋃ P 3 . Since n ≥ 5 and l ≥ 4, we have F ⊆ G , a contradiction. By Lemma 2.2, l ≥ 2 h . Furthermore, since n ≥ 2 h +3 and P 2 h +3 /notsubseteql G , we have l ≤ 2 h +1. So 2 h ≤ l ≤ 2 h +1. We consider the following two subcases.

Subcase 1.1: l = 2 h . Since P 2 h +3 /notsubseteql G , we have P 3 /notsubseteql G U [ ]. If U is an independent set, then Lemma 2.4 ( ) implies i G ⊆ S n,h . Now we assume that G U [ ] consists of p disjoint edges and q isolated vertices, i.e., u u , u 1 2 3 u , . . . , u 4 2 p -1 u 2 p , w 1 , . . . , w q , where p ≥ 1 and q ≥ 0. By Lemma 2.5 ( ), i N C 2 h ( u 2 i -1 ) = N C 2 h ( u 2 i ) for 1 ≤ i ≤ p . Note that d C 2 h ( u j ) = d G ( u j ) -1 ≥ h -1 for 1 ≤ j ≤ 2 p . Since C 2 h is a longest cycle in G , the distance along C 2 h between two vertices in N C 2 h ( u 1 ) is at least 3, which implies 3( h -1) ≤ 2 h . Thus h ≤ 3. Furthermore, h = 3 (Otherwise h = 2, which implies d C 4 ( u i ) = 1 and d G ( u i ) = 2 for 1 ≤ i ≤ 2. Thus the common neighbor of u 1 and u 2 in V ( C 4 ) is a cut vertex, which contradicts that G is 2-connected). Now let A = { P 6 ⋃ P , P 3 4 ⋃ P , P 5 2 ⋃ P , P 7 4 ⋃ P 2 ⋃ P , 3 2 P 2 ⋃ P , 5 3 P 2 ⋃ P 3 } . Since h = 3 and k ≥ 1, we have F ∈ A . Moreover, d C 6 ( u 2 i -1 ) = d C 6 ( u 2 i ) = 2 and d G ( u 2 i -1 ) = d G ( u 2 i ) = 3 for 1 ≤ i ≤ p . Since C 6 is a longest cycle in G , we assume without loss of generality that N C 6 ( u 1 ) = N C 6 ( u 2 ) = { v , v 1 4 } . Since F /notsubseteql G , we have N C 6 ( u 2 i -1 ) = N C 6 ( u 2 i ) = { v , v 1 4 } for 1 ≤ i ≤ p . Next we claim that q = 0. In fact, if q ≥ 1, then d G ( w 1 ) = d C 6 ( w 1 ) = 3, which implies F ⊆ G , a contradiction. So n must be even. Hence G ⊆ K 2 ∨ n -2 2 K 2 . Moreover, F = P 6 ⋃ P 3 . The assertion holds.

Subcase 1.2: l = 2 h +1. By the proof of Lemma 2.4 ( ii ), we have N C 2 h +1 ( u ) = { v , v 2 4 , . . . , v 2 h } for every u ∈ U . Hence there exist two disjoint paths uv v 2 3 · · · v 2 b 1 +1 and wv 2 b 1 +2 · · · v 2 h +1 v 1 for two different vertices u, w ∈ U . Hence F ⊆ G and it is a contradiction.

Case 2: G has at least one cut vertex. If h = 1, then F = P 2 ⋃ P 3 . Since F /notsubseteql G G , must be a star K 1 ,n -1 , i.e., G = L n -1 1 , . Now we assume that h ≥ 2. First we prove the following three Claims.

$$\begin{array} { l } \tilde { \text{Claim 1} } \colon P _ { h + 1 } \bigcup P _ { 2 h + 1 } \nmid G. \\ \text{Suppose $P_{h+1}|\, |\, P_{h+1} \subset G.\ If $\sum_{i-1}^{k} a_{i}>$} \end{array}$$

Suppose P h +1 ⋃ P 2 h +1 ⊆ G . If ∑ i =1 a i ≥ b 1 +1, then

$$h + 1 = \sum _ { i = 1 } ^ { k } a _ { i } + b _ { 1 } \geq 2 b _ { 1 } + 1$$

and

$$2 h + 1 \geq \sum _ { i = 1 } ^ { k } 2 a _ { i } + 2 b _ { 1 } - 1 \geq \sum _ { i = 1 } ^ { k } 2 a _ { i }.$$

Thus F ⊆ G , a contradiction. If ∑ k i =1 a i ≤ b 1 , then

$$h + 1 = \sum _ { i = 1 } ^ { k } a _ { i } + b _ { 1 } \geq \sum _ { i = 1 } ^ { k } 2 a _ { i }$$

and

$$2 h + 1 \geq \sum _ { i = 1 } ^ { k } 2 a _ { i } + 2 b _ { 1 } - 1 \geq 2 b _ { 1 } + 1.$$

Thus F ⊆ G , a contradiction. So Claim 1 holds.

Claim 2 : | V ( B ) | = h +1 for every end block B of G .

Since δ G ( ) ≥ h , it follows that | V ( B ) | ≥ h +1 for every end block B of G . Next we prove that | V ( B ) | ≤ h +1 for every end block B of G . Suppose that there exists an end block B 1 of order at least h +2. If there exists another end block B 2 such that V ( B 1 ) ⋂ V ( B 2 ) = ∅ , then Lemma 2.1 implies P 2 h +3 ⊆ G , a contradiction. If there exist another two end blocks B 2 and B 3 such that B , B , 1 2 and B 3 share a common cut vertex u of G , then Lemma 2.1 implies that there exist three paths P h +2 , P h +1 , and P h +1 in B , B 1 2 and B 3 with an end vertex u , respectively. Hence P h +1 ⋃ P 2 h +1 ⊆ G , a contradiction. These discussions imply that there are exactly two blocks B 1 and B 2 sharing one common cut vertex u of G , where | V ( B 1 ) | ≥ h +2 and | V ( B 2 ) | = n -| V ( B 1 ) | +1. By Lemma 2.1, there exist two paths P l 1 and P l 2 with an end vertex u in B 1 and B 2 , respectively, where l 1 ≥ min {| V ( B 1 ) | , 2 h } and l 2 ≥ min {| V ( B 2 ) | , 2 h } . Hence P 2 h +3 ⊆ G , a contradiction. Therefore Claim 2 holds.

Claim 3 : G = L t,h , where n = th +1 and F ∈ { P 2 b ⋃ P 2 b +1 , P 2 b +2 ⋃ P 2 b +1 } .

1 1 1 1 Choose two end blocks B 1 and B 2 of G such that p B , B ( 1 2 ) is as large as possible, where p B , B ( 1 2 ) is the order of a longest path between the unique cut vertex u 1 of G in V ( B 1 ) and the unique cut vertex u 2 of G in V ( B 2 ). By Claim 2, | V ( B 1 ) | = | V ( B 2 ) | = h +1. If p B , B ( 1 2 ) ≥ 3, then Lemma 2.1 implies P 2 h +3 ⊆ G , a contradiction. Since n ≥ 2 h +3, if p B , B ( 1 2 ) = 2 then there exists another end block B 3 of G , sharing a common vertex u 1 with B 1 or a common vertex u 2 with B 2 . By Lemma 2.1, P h +1 ⋃ P 2 h +1 ⊆ G , which contradicts Claim 1. Hence all blocks share a common cut vertex of G , i.e., G = L t,h , where n = th +1. Moreover, P h ⋃ P 2 h +1 ⊆ G , P h -1 ⋃ P h ⋃ P h +2 ⊆ G , and P h ⋃ P h ⋃ P h +1 ⊆ G . If ∑ k i =1 a i ≥ b 1 +2, then

$$h = \sum _ { i = 1 } ^ { k } a _ { i } + b _ { 1 } - 1 \geq 2 b _ { 1 } + 1,$$

and

$$2 h + 1 = \sum _ { i = 1 } ^ { k } 2 a _ { i } + 2 b _ { 1 } - 1 \geq \sum _ { i = 1 } ^ { k } 2 a _ { i }.$$

Hence F ⊆ G , a contradiction. If ∑ k i =1 a i ≤ b 1 -1, then

$$h = \sum _ { i = 1 } ^ { k } a _ { i } + b _ { 1 } - 1 \geq \sum _ { i = 1 } ^ { k } 2 a _ { i },$$

and

$$2 h + 1 = \sum _ { i = 1 } ^ { k } 2 a _ { i } + 2 b _ { 1 } - 1 \geq 2 b _ { 1 } + 1.$$

Hence F ⊆ G , a contradiction. If ∑ k i =1 a i = b 1 and k ≥ 2, then

$$h - 1 = \sum _ { i = 1 } ^ { k } 2 a _ { i } - 2 \geq 2 a _ { k },$$

$$h = \sum _ { i = 1 } ^ { k } 2 a _ { i } - 1 > \sum _ { i = 1 } ^ { k - 1 } 2 a _ { i },$$

and

$$h + 2 = \sum _ { i = 1 } ^ { k } a _ { i } + b _ { 1 } + 1 = 2 b _ { 1 } + 1.$$

Hence F ⊆ G , a contradiction. If ∑ k i =1 a i = b 1 +1 and k ≥ 2, then

$$h = \sum _ { i = 1 } ^ { k } 2 a _ { i } - 2 \geq \sum _ { i = 1 } ^ { k - 1 } 2 a _ { i },$$

$$h = \sum _ { i = 1 } ^ { k } 2 a _ { i } - 2 \geq 2 a _ { k },$$

and

$$h + 1 = \sum _ { i = 1 } ^ { k } a _ { i } + b _ { 1 } = 2 b _ { 1 } + 1. \\.. \. \. \. \. \. \.$$

Hence F ⊆ G , a contradiction. So we have F ∈ { P 2 b 1 ⋃ P 2 b 1 +1 , P 2 b 1 +2 ⋃ P 2 b 1 +1 } and G = L t,h , where n = th +1. /square

## 4 Proofs of Theorems 1.10 and 1.11

We will use the next several lemmas in Theorem 1.10.

Lemma 4.1. Let G be a connected graph of order n .

(i). If δ G ( ) ≥ 1 and n ≥ 6 , then 2 P 3 ⊆ G , unless either G = U 3 1 , , or G ⊆ L t 1 ,t 2 , 1 2 , for n = t 1 +2 t 2 +1 .

(ii). If δ G ( ) ≥ 2 and n ≥ 8 , then P 5 ⋃ P 3 ⊆ G , unless G ⊆ S + n, 2 , G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 for n = 2 t +1 .

(iii). If δ G ( ) ≥ 2 and n ≥ 8 , then P 2 ⋃ 2 P 3 ⊆ G , unless either G ⊆ S n, 2 , or G = L t, 2 for n = 2 t +1 .

/negationslash

/negationslash

Proof. ( ). i Suppose 2 P 3 /notsubseteql G . Let P l be a longest path in G , denoted by v v 1 2 · · · v l . Since n ≥ 6 and 2 P 3 /notsubseteql G , we have 3 ≤ l ≤ 5. If l = 3, then G must be a star K 1 ,n -1 , i.e., G = L n -1 1 , . Since n ≥ 6 and 2 P 3 /notsubseteql G , if l = 4 then G ⊆ L n -3 1 1 2 , , , . Next we assume that l = 5. Since 2 P 3 /notsubseteql G , we have N P 5 ( u ) ⊆ { v 3 } for all u ∈ V ( G ) \ V ( P 5 ). Let X ⊆ V ( G ) \ V ( P 5 ) such that N P 5 ( u ) = { v 3 } for all u ∈ X and Y = V ( G ) \ ( V ( P 5 ) ⋃ X ). Since n ≥ 6 and 2 P 3 /notsubseteql G , we have X = ∅ and P 3 /notsubseteql G X [ ]. So we can assume that G X [ ] consists of p disjoint edges and q isolated vertices, i.e., u u , . . . , u 1 2 2 p -1 u 2 p , w 1 , . . . , w q , where p + q ≥ 1. Since P 5 is a longest path in G Y , must be an independent set if | Y | ≥ 1. Furthermore, N G ( u ) = { w i } and N G ( v ) = { w j } for any two distinct vertices u, v ∈ Y (it also holds for | Y | = 1), where 1 ≤ i, j ≤ q and i = . Moreover, j v v 1 4 , v v 1 5 , v v 2 5 / E G ∈ ( ), otherwise 2 P 3 ⊆ G , a contradiction. Since 2 P 3 /notsubseteql G , if v v 2 4 ∈ E G ( ) then v v 1 3 / E G ∈ ( ), | Y | = p = 0, and q = 1, which implies that G = U 3 1 , . If v v 2 4 / E G ∈ ( ), then G ⊆ L t 1 ,t 2 , 1 2 , , where n = t 1 +2 t 2 +1. Thus the assertion holds.

( ii ). Suppose P 5 ⋃ P 3 /notsubseteql G . Let C l be a longest cycle in G , denoted by v v 1 2 · · · v v l 1 , and U = V ( G ) \ V ( C l ). Since C l is a longest cycle, none of vertices in U is adjacent to any two consecutive vertices of C l . Since n ≥ 8 and P 5 ⋃ P 3 /notsubseteql G , it follows that 3 ≤ l ≤ 6. We consider the following four cases.

Case 1 : l = 3. This implies that all cycles in G are triangles. Since δ G ( ) ≥ 2, G has at least two triangles. Let T 1 and T 2 be two triangles in G such that the longest path P k , denoted by u u 1 2 · · · u k , with V ( P k ) ⋂ V ( T 1 ) = { u 1 } and V ( P k ) ⋂ V ( T 2 ) = { u k } , is as long as possible. Since n ≥ 8, δ G ( ) ≥ 2, and P 5 ⋃ P 3 /notsubseteql G , it follows that 1 ≤ k ≤ 2. More precisely, k = 1 (Otherwise k = 2. P 5 ⋃ P 3 /notsubseteql G together with δ G ( ) ≥ 2 implies that d G ( w ) = { u , u 1 2 } for every w ∈ V ( G ) \ ⋃ 2 i =1 V ( T i ). Then | V ( G ) \ ⋃ 2 i =1 V ( T i ) | = 1, i.e., n = 7, which contradicts that n ≥ 8.). So all triangles in G share a common vertex. Since δ G ( ) ≥ 2, G = L t, 2 for n = 2 t +1.

Case 2 : l = 4. Let P k , denoted by u 1 · · · u k , be a longest path in G U [ ]. Since P 5 ⋃ P 3 /notsubseteql G , it follows that 1 ≤ k ≤ 4. we consider the following four subcases.

/negationslash

/negationslash

Subcase 2.2: k = 3. By Lemma 2.5 (ii), N C 4 ( u 1 ) = N C 4 ( u 3 ). Since C 4 is a longest cycle, d C 4 ( u 1 ) = d C 4 ( u 3 ) = 1. Note that n ≥ 8. We have P 5 ⋃ P 3 ⊆ G , a contradiction.

Subcase 2.1: k = 4. Since P 5 ⋃ P 3 /notsubseteql G , it follows that N C 4 ( u 1 ) = N C 4 ( u 4 ) = ∅ . Since G is connected, either N C 4 ( u 2 ) = ∅ or N C 4 ( u 3 ) = ∅ . If u u 1 4 ∈ E G ( ), then P 5 ⋃ P 3 ⊆ G , a contradiction. Since δ G ( ) ≥ 2, if u u 1 4 / E G ∈ ( ) then u u 1 3 ∈ E G ( ) and u u 2 4 ∈ E G ( ). Thus P 5 ⋃ P 3 ⊆ G , a contradiction.

Subcase 2.3: k = 2. Obviously, G U [ ] consists of p disjoint edges and q isolated vertices, i.e., u u , u 1 2 3 u , . . . , u 4 2 p -1 u 2 p , w 1 , . . . , w q , where p ≥ 1, q ≥ 0 and 2 p + q = n -4. Since C 4 is a longest cycle, Lemma 2.5 ( ) implies that i N C 4 ( u 2 i -1 ) = N C 4 ( u 2 i ) and d C 4 ( u 2 i -1 ) = d C 4 ( u 2 i ) = 1 for 1 ≤ i ≤ p . So we assume without loss of generality that N C 4 ( u 1 ) = N C 4 ( u 2 ) = { v 1 } . Since C 4 is a longest cycle and δ G ( ) ≥ 2, it follows that N C 4 ( w 1 ) = · · · = N C 4 ( w r ) = { v , v 1 3 } and N C 4 ( w r +1 ) = . . . = N C 4 ( w r + t ) = { v , v 2 4 } , where r + t = q . Moreover, since P 5 ⋃ P 3 /notsubseteql G , if p ≥ 2 then N C 4 ( u 3 ) = N C 4 ( u 4 ) = { v 3 } , p = 2, and t = 0. Thus G ⊆ H 2 n . In addition, since P 5 ⋃ P 3 /notsubseteql G and r + t = q ≥ 2, if p = 1 then t = 0. Thus G ⊆ H 1 n .

Subcase 2.4: k = 1. Obviously, the graph G U [ ] consists of q isolated vertices, i.e., w , . . . , w 1 q , where q = n -4 ≥ 4. Since C 4 is a longest cycle and δ G ( ) ≥ 2, N C 4 ( w 1 ) = · · · = N C 4 ( w r ) = { v , v 1 3 } and N C 4 ( w r +1 ) = · · · = N C 4 ( w r + t ) = { v , v 2 4 } , where r + = t q ≥ 4. We assume without loss of generality that r ≥ t . It follows that t = 0, otherwise P 5 ⋃ P 3 ⊆ G , a contradiction. Furthermore, since P 5 ⋃ P 3 /notsubseteql G , we

also have v v 2 4 / E G ∈ ( ). Thus G ⊆ S n, 2 .

Case 3: l = 5. Since P 5 ⋃ P 3 /notsubseteql G , we have P 3 /notsubseteql G U [ ]. Furthermore, U is an independent set (Otherwise, the graph G U [ ] contains an edge u u 1 2 . Since C 5 is a longest cycle, Lemma 2.5 (i) implies that N C 5 ( u 1 ) = N C 5 ( u 2 ) and d C 5 ( u 1 ) = d C 5 ( u 2 ) = 1. Note that n ≥ 8 and δ G ( ) ≥ 2. We have P 5 ⋃ P 3 ⊆ G , a contradiction.). Since n ≥ 8 and δ G ( ) ≥ 2, the longest cycle C 5 together with P 5 ⋃ P 3 /notsubseteql G implies that N C 5 ( u 1 ) = N C 5 ( u 2 ) and d C 5 ( u 1 ) = d C 5 ( u 2 ) = 2 for any two vertices u , u 1 2 ∈ U . We assume without loss of generality that N C 5 ( u ) = { v , v 1 3 } for all u ∈ U . Since P 5 ⋃ P 3 /notsubseteql G G , [ { v , v 2 4 , v 5 } ] contains exactly one edge v v 4 5 . Hence G ⊆ S + n, 2 . Thus the assertion holds.

( iii ). Suppose P 2 ⋃ 2 P 3 /notsubseteql G . This implies P 5 ⋃ P 3 /notsubseteql G . By Lemma 4.1 ( ii ), either G ⊆ S + n, 2 , G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 for n = 2 +1. However, if t G = S + n, 2 , G ⊆ H 1 n , or G ⊆ H 2 n , then P 2 ⋃ 2 P 3 ⊆ G , a contradiction. Hence either G ⊆ S n, 2 , or G = L t, 2 for n = 2 t +1. Thus the assertion holds. /square

Case 4: l = 6. Let U = V ( G ) \ V ( C 6 ). Since P 5 ∪ P 3 /notsubseteql G , we have P 8 /notsubseteql G . By Lemma 2.4 ( iii ), N C 6 ( u ) = N C 6 ( v ) for any two vertices u, v ∈ U and 2 ≤ d C 6 ( u ) = d C 6 ( v ) ≤ 3. Since P 5 ⋃ P 3 /notsubseteql G , it follows that d C 6 ( u ) = d C 6 ( v ) = 2 and the distance along C 6 between two vertices in N C 6 ( u ) is at least 3. However, we also have P 5 ⋃ P 3 ⊆ G , a contradiction.

Lemma 4.2. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 ≥ 3 , and G be a connected graph of order n with a longest cycle C l , where k ≥ 0 , a 1 ≥ · · · ≥ a k ≥ 1 , b 1 ≥ b 2 ≥ 1 , and n ≥ 2 h + 4 . If δ G ( ) ≥ h and F /notsubseteql G , then 2 h ≤ l ≤ 2 h +1 .

Proof. Let C l = v v 1 2 · · · v v l 1 . By Lemma 2.2, l ≥ 2 h . Since ∑ k i =1 2 a i + ∑ 2 i =1 (2 b i + 1) = 2 h + 4 and F /notsubseteql G , we have P 2 h +4 /notsubseteql G . Note that G is connected and n ≥ 2 h + 4. So l ≤ 2 h + 2. We now prove l ≤ 2 h + 1. Suppose that l = 2 h + 2. Let U = V ( G ) \ V ( C 2 h +2 ). By Lemma 2.4 ( iii ), all vertices in U have the same C 2 h +2 -neighborhood, denoted by V 1 , and h ≤ | V 1 | ≤ h +1. Let V 2 = V ( C 2 h +2 ) \ V 1 . We consider the following two cases.

Case 1: | V 1 | = h + 1. Since C 2 h +2 is a longest cycle, none of vertices in U is adjacent to any two consecutive vertices in V ( C 2 h +2 ). So we assume without loss of generality that V 1 = { v , v 1 3 , . . . , v 2 h +1 } . Let H , i.e., H = ( X,Y ; E ), be a bipartite subgraph of G , where X = V 1 \ { v 2 h +1 } and Y ⊆ U with | Y | = h +2 and | U | = | V ( G ) | - | V ( C 2 h +2 ) | ≥ h +2. By definition, H must be a complete bipartite graph. Moreover, let G 1 be the graph obtained from H by identifying v 2 h -1 with a path P 4 , v 2 h -1 v 2 h v 2 h +1 v 2 h +2 . By Lemma 2.6 ( ii ), we have F ⊆ G , a contradiction.

Case 2: | V 1 | = h . Since none of vertices in U is adjacent to any two consecutive vertices in V ( C 2 h +2 ), there exist two edges e , e 1 2 ∈ E C ( 2 h +2 ) whose end vertices are all in V 2 . If e 1 and e 2 share a common vertex, then we assume without loss of generality that e 1 = v 2 h v 2 h +1 and e 2 = v 2 h +1 v 2 h +2 . This implies that V 1 = { v , . . . , v 1 2 h -1 } and v 2 h v 2 h +1 v 2 h +2 ⊆ G V [ 2 ]. By Lemma 2.6 ( ii ), F ⊆ G , a contradiction. So e 1 and e 2 share no vertex in common. We assume without loss of generality that e 1 = v v 1 2 and e 2 = v 2 +2 s v 2 +3 s , where 1 ≤ s ≤ h -1. Let W = V 2 \{ v , v 1 2 , v 2 +2 s , v 2 +3 s } . Furthermore, we claim that W is an independent set. In fact, if v v p q ∈ E G ( ), where v , v p q ∈ W , then uv p -1 v p -2 · · · v v v q p p +1 · · · v q -1 u is a longer cycle than C 2 h +2 with u ∈ U , a contradiction. Moreover, since F /notsubseteql G , Lemma 2.6 ( ii ) implies that G V [ 2 ] contains exactly two disjoint edges e 1 and e 2 . Thus for every u ∈

{ v , v 1 2 , v 2 +2 s , v 2 +3 s } , N G ( u ) ⋂ V 1 ≥ h -1 ≥ 2 and | N G ( v 1 ) ⋂ N G ( v 2 +2 s ) ⋂ V 1 | ≥ h -2 ≥ 1. Choose v ∈ N G ( v 1 ) ⋂ N G ( v 2 +2 s ) ⋂ V 1 . Note that v v vv 2 1 2 +2 s v 2 +3 s ⊆ G and v 2 has a neighbor different from v in V 1 . By Lemma 2.6 ( iii ), F ⊆ G , a contradiction.

Hence the assertion holds. /square

Lemma 4.3. Let F = ⋃ 2 i =1 P 2 b i +1 , h = ∑ 2 i =1 b i -1 ≥ 3 and G be a connected graph of order n with a longest cycle C 2 h , where b 1 ≥ b 2 ≥ 1 and n ≥ 2 h +4 . If δ G ( ) ≥ h and F /notsubseteql G , then P 3 /notsubseteql G U [ ] , where U = V ( G ) \ V ( C 2 h ) .

Proof. Let C 2 h = v v 1 2 · · · v 2 h v 1 . Since ∑ 2 i =1 (2 b i +1) = 2 h +4 and F /notsubseteql G , we have P 2 h +4 /notsubseteql G . We first prove the following two Claims.

Claim 1: P 4 /notsubseteql G U [ ].

/negationslash

Suppose P 4 ⊆ G U [ ]. Since P 2 h +4 /notsubseteql G , there exists one path P 4 , denoted by u u u u 1 2 3 4 , such that N C 2 h ( u 1 ) = N C 2 h ( u 4 ) = ∅ , and either N C 2 h ( u 2 ) = ∅ or N C 2 h ( u 3 ) = ∅ . Furthermore, since P 2 h +4 /notsubseteql G , either N G ( u 1 ) = { u , u 2 3 } or N G ( u 4 ) = { u , u 2 3 } . So d G ( u 1 ) = 2 or d G ( u 4 ) = 2, which contradicts that δ G ( ) ≥ h ≥ 3. So Claim 1 holds.

/negationslash

Claim 2: P 3 /notsubseteql G U [ ].

Suppose P 3 ⊆ G U [ ]. Let P 3 = u u u 1 2 3 ⊆ G U [ ]. By Claim 1, P 4 /notsubseteql G U [ ], and thus by Lemma 2.5 ( ii ), N C 2 h ( u 1 ) = N C 2 h ( u 3 ). Moreover, d C 2 h ( u 1 ) ≥ d G ( u 1 ) -2 ≥ h -2 and d C 2 h ( u 3 ) ≥ d G ( u 3 ) -2 ≥ h -2. Since C 2 h is a longest cycle in G , the distance along C 2 h between any two vertices in N C 2 h ( u 1 ) is at least 4, which implies that 4( h -2) ≤ 2 h . Thus 3 ≤ h ≤ 4. We consider the following two cases.

/negationslash

Case 1: h = 4. Obviously, either F = P 9 ⋃ P 3 or F = P 7 ⋃ P 5 . It is easy to see that d C 8 ( u 1 ) = d C 8 ( u 3 ) = 2, d G ( u 1 ) = d G ( u 3 ) = 4, and the distance along C 8 between two vertices in N C 8 ( u 1 ) is exactly 4. Hence we assume without loss of generality that N C 8 ( u 1 ) = N C 8 ( u 3 ) = { v , v 1 5 } . Since P 4 /notsubseteql G U [ ], we have u u 1 3 ∈ E G ( ). Note that n ≥ 12 in this case. So U \{ u , u 1 2 , u 3 } = ∅ . Since F /notsubseteql G and P 4 /notsubseteql G U [ ], u is adjacent to none of vertices in V ( C 8 ) ⋃ { u , u 1 2 , u 3 } for all u ∈ U \{ u , u 1 2 , u 3 } , which contradicts that G is connected.

Case 2: h = 3. Obviously, either F = P 7 ⋃ P 3 or F = 2 P 5 . It is easy to see that d C 6 ( u 1 ) = d C 6 ( u 3 ) = 1 and d G ( u 1 ) = d G ( u 3 ) = 3. We assume without loss of generality that N C 6 ( u 1 ) = N C 6 ( u 3 ) = { v 1 } . Note that P 4 /notsubseteql G U [ ]. We have u u 1 3 ∈ E G ( ). Note that n ≥ 10 in this case. So U \{ u , u 1 2 , u 3 } /negationslash = ∅ . Furthermore, since F /notsubseteql G , it follows that N C ( u ) ⋂ { v , v 1 2 , v 3 , v 5 , v 6 } = ∅ for all u ∈ U \{ u , u 1 2 , u 3 } . Hence N C 6 ( u ) ⊆ { v 4 } . Moreover, since P 4 /notsubseteql G U [ ], u is not adjacent to any vertex in { u , u 1 2 , u 3 } . Thus the connectedness of G implies that there exists u 0 ∈ U \{ u , u 1 2 , u 3 } such that N C 6 ( u 0 ) = { v 4 } . However, since δ G ( ) ≥ 3, there exists another vertex w ∈ U \{ u , u 1 2 , u 3 } such that u w 0 ∈ E G ( ). Therefore F ⊆ G , a contradiction.

Thus the assertion holds. /square

Corollary 4.4. Let F = ⋃ 2 i =1 P 2 b i +1 , h = ∑ 2 i =1 b i -1 ≥ 3 , and G be a connected graph of order n with a longest cycle C 2 h , where b 1 ≥ b 2 ≥ 1 and n ≥ 2 h + 4 . If δ G ( ) ≥ h , then F ⊆ G , unless either G ⊆ S n,h , or F = P 7 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 for even n .

Proof. Suppose F /notsubseteql G . Let C 2 h = v v 1 2 · · · v 2 h v 1 and U = V ( G ) \ V ( C 2 h ). By Lemma 4.2, P 3 /notsubseteql G U [ ]. If U is an independent set, then Lemma 2.4 ( ) implies i G ⊆

S n,h . Hence we assume that G U [ ] consists of p disjoint edges and q isolated vertices, i.e., u u , u 1 2 3 u , . . . , 4 u 2 p -1 u 2 p , w 1 , . . . , w q , where p ≥ 1 and q ≥ 0. By Lemma 2.5 ( ), i N C 2 h ( u 2 i -1 ) = N C 2 h ( u 2 i ) for 1 ≤ i ≤ p . Furthermore, d C 2 h ( u j ) = d G ( u j ) -1 ≥ h -1 for 1 ≤ j ≤ 2 p . Since C 2 h is a longest cycle, the distance along C 2 h between any two vertices in N C 2 h ( u 1 ) is at least 3, which implies that 3( h -1) ≤ 2 h . Thus h = 3. It follows that either F = P 7 ⋃ P 3 or F = 2 P 5 , and d C 6 ( u j ) = 2 for 1 ≤ j ≤ 2 p . Moreover, the distance along C 6 between two vertices in N C 6 ( u 1 ) is exactly 3. Hence we assume without loss of generality that N C 6 ( u 1 ) = N C 6 ( u 2 ) = { v , v 1 4 } . Since F /notsubseteql G , it follows that N C 6 ( u 2 i -1 ) = N C 6 ( u 2 i ) = { v , v 1 4 } for 1 ≤ i ≤ p . Next we prove that q = 0. In fact, since n ≥ 10, if q ≥ 1 then either p = 1 and q ≥ 2, or p ≥ 2 and q ≥ 1. If p = 1 and q ≥ 2, then d G ( w i ) = d C 6 ( w i ) = 3 for 1 ≤ i ≤ 2 and thus F ⊆ G , a contradiction. If p ≥ 2 and q ≥ 1, then d G ( w 1 ) = d C 6 ( w 1 ) = 3, and thus F ⊆ G , a contradiction. So n must be even. In addition, since F /notsubseteql G G , [ { v , v 2 3 , v 5 , v 6 } ] consists of two disjoint edges v v 2 3 and v v 5 6 . Therefore G ⊆ K 2 ∨ n -2 2 K 2 . Moreover, F = P 7 ⋃ P 3 . Thus the assertion holds.

Corollary 4.5. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 ≥ 3 , and G be a connected graph of order n with a longest cycle C 2 h , where k ≥ 1 , b 1 ≥ b 2 ≥ 1 , and n ≥ 2 h +4 . If δ G ( ) ≥ h , then F ⊆ G unless, either G ⊆ S n,h , or F = P 4 ⋃ 2 P 3 and G ⊆ K 2 ∨ n -3 2 K 2 for even n .

Proof. Suppose F /notsubseteql G . Let F ′ = ⋃ 2 i =1 P 2 b ′ i +1 , where b ′ 1 = ∑ k i =1 a i + b 1 and b ′ 2 = b 2 . We have F ′ /notsubseteql G . By Corollary 4.4, either G ⊆ S n,h , or F ′ = P 7 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 for even n . Note F /notsubseteql G whenever G ⊆ S n,h . So we assume that F ′ = P 7 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 for even n . Then we have F ∈ { P 4 ⋃ 2 P , P 3 2 ⋃ P 5 ⋃ P , 3 2 P 2 ⋃ 2 P 3 } . In addition, P 2 ⋃ P 5 ⋃ P 3 ⊆ G , 2 P 2 ⋃ 2 P 3 ⊆ G , and P 4 ⋃ 2 P 3 /notsubseteql G . Hence F = P 4 ⋃ 2 P 3 . Thus the assertion holds.

Lemma 4.6. Let F = ⋃ 2 i =1 P 2 b i +1 , h = ∑ 2 i =1 b i -1 ≥ 3 , and G be a connected graph of order n with a longest cycle C 2 h +1 , where b 1 ≥ b 2 ≥ 1 and n ≥ 4(2 h +1) 2 ( 2 h +1 h ) . If δ G ( ) ≥ h , then F ⊆ G , unless either G ⊆ S + n,h , or F = P 9 ⋃ P 3 and G ⊆ K 3 ∨ n -3 2 K 2 for odd n .

Proof. Suppose F /notsubseteql G . Since ∑ 2 i =1 (2 b i + 1) = 2 h + 4, we have P 2 h +4 /notsubseteql G . Let C 2 h +1 = v v 1 2 · · · v 2 h +1 v 1 and U = V ( G ) \ V ( C 2 h +1 ). We consider the following two cases.

/negationslash

Case 1: U is an independent set. Since C 2 h +1 is a longest cycle, none of vertices in U is adjacent to any two consecutive vertices along C 2 h +1 . It follows that d C 2 h +1 ( u ) = h for all u ∈ U . By Lemma 2.3, there exists V 1 ⊆ V ( C 2 h +1 ) and U 1 ⊆ U with | V 1 | = h and | U 1 | = h + 2 such that H V ,U ( 1 1 ; E ) is a complete bipartite graph. Hence N C 2 h +1 ( u ) = V 1 for all u ∈ U 1 . We assume without loss of generality that V 1 = { v , v 2 4 , . . . , v 2 h } . Moreover, N C 2 h +1 ( u ) = V 1 for all u ∈ U U \ 1 . Otherwise, there exists u ∈ U U \ 1 such that N C 2 h +1 ( u ) ⋂ ( V ( C 2 h +1 ) \ V 1 ) = ∅ . Since u is not adjacent to any two consecutive vertices along C 2 h +1 , we have v 1 or v 2 h +1 ∈ N C 2 h +1 ( u ) ⋂ ( V ( C 2 h +1 ) \ V 1 ). Note v , v 2 2 h ∈ V 1 and v v 1 2 h +1 ∈ E G ( ). By Lemma 2.6 ( ii ), F ⊆ G , a contradiction. Furthermore, { v , v 1 3 , . . . , v 2 h -1 } is an independent set (Othewise, let v 2 +1 s v 2 +1 t ∈ E G ( ) and u ∈ U , where 1 ≤ 2 s +1 &lt; 2 t +1 ≤ 2 h -1. It follows that uv 2 s v 2 s -1 · · · v v v 2 1 2 h +1 v 2 h · · · v 2 +2 t v 2 +1 t v 2 +1 s v 2 +2 s · · · v 2 t -1 v 2 t u is a

longer cycle than C 2 h +1 , a contradiction). Similarly, { v , . . . , v 3 2 h +1 } is an independent set. Hence G v ,v ,... , v [ { 1 3 2 h +1 } ] contains exactly one edge v v 1 2 h +1 . Thus G ⊆ S + n,h .

Case 2: G U [ ] contains at least one edge. Since δ G ( ) ≥ 2, we have P 3 /notsubseteql G U [ ]. Hence we assume that G U [ ] consists of p disjoint edges and q isolated vertices, i.e., u u , u 1 2 3 u , . . . , u 4 2 p -1 u 2 p , w 1 , . . . , w q , where p ≥ 1 and q ≥ 0. By Lemma 2.5 ( ), i N C 2 h +1 ( u 2 i -1 ) = N C 2 h +1 ( u 2 i ) for 1 ≤ i ≤ p . Furthermore, d C 2 h +1 ( u j ) = d G ( u j ) -1 ≥ h -1 for 1 ≤ j ≤ 2 p . Since C 2 h +1 is a longest cycle in G , the distance along C 2 h +1 between any two vertices in N C 2 h +1 ( u 1 ) is at least 3, which implies that 3( h -1) ≤ 2 h + 1. Thus 3 ≤ h ≤ 4. We claim that h = 4 (Otherwise h = 3 and thus either F = P 7 ⋃ P 3 or F = 2 P 5 . Moreover, the distance along C 7 between two vertices in N C 7 ( u 1 ) is exactly 3. So we assume without loss of generality that N C 7 ( u 1 ) = N C 7 ( u 2 ) = { v , v 1 4 } . Since F /notsubseteql G , it follows that N C 7 ( u ) ⋂ { v , v 1 2 , v 3 , v 4 , v 5 , v 7 } = ∅ for all u ∈ U \{ u , u 1 2 } . Hence N C 7 ( u ) ⊆ { v 6 } , which contradicts d C 7 ( u ) ≥ 2.). Hence either F = P 9 ⋃ P 3 or F = P 7 ⋃ P 5 . Moreover, the distance along C 9 between any two vertices in N C 9 ( u 1 ) is exactly 3. So we assume without loss of generality that N C 9 ( u 1 ) = N C 9 ( u 2 ) = { v , v 1 4 , v 7 } . Since F /notsubseteql G , it follows that N C 9 ( u 2 i -1 ) = N C 9 ( u 2 i ) = { v , v 1 4 , v 7 } for 1 ≤ i ≤ p , and q = 0. So n must be odd. In addition, since F /notsubseteql G G , [ { v , v 2 3 , v 5 , v 6 , v 8 , v 9 } ] consists of three disjoint edges v v 2 3 , v v 5 6 and v v 8 9 . Therefore G = K 3 ∨ n -3 2 K 2 . Moreover, F = P 9 ⋃ P 3 . Thus the assertion holds. /square

Lemma 4.7. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 ≥ 3 , and G be a connected graph of order n with a longest cycle C 2 h +1 , where k ≥ 1 , b 1 ≥ b 2 ≥ 1 , and n ≥ 4(2 h +1) 2 ( 2 h +1 h ) . If δ G ( ) ≥ h , then F ⊆ G , unless F = P 6 ⋃ 2 P 3 and G ⊆ K 3 ∨ n -3 2 K 2 for odd n .

Proof. Suppose F /notsubseteql G . Let F ′ = ⋃ 2 i =1 P 2 b ′ i +1 , where b ′ 1 = ∑ k i =1 a i + b 1 and b ′ 2 = b 2 . We have F ′ /notsubseteql G . By Lemma 4.6, either G ⊆ S + n,h , or F ′ = P 9 ⋃ P 3 and G ⊆ K 3 ∨ n -3 2 K 2 for odd n . If G ⊆ S + n,h , then F ⊆ G , a contradiction. Thus we assume that F ′ = P 9 ⋃ P 3 and G ⊆ K 3 ∨ n -3 2 K 2 for odd n . Hence F ∈ { P 2 ⋃ P 7 ⋃ P , P 3 2 ⋃ 2 P , P 5 4 ⋃ P 5 ⋃ P , P 3 6 ⋃ 2 P , 3 2 P 2 ⋃ P 5 ⋃ P , P 3 4 ⋃ P 2 ⋃ 2 P , 3 3 P 2 ⋃ 2 P 3 } . In addition, since F /notsubseteql G , it follows that F = P 6 ⋃ 2 P 3 . Thus the assertion holds.

Theorem 1.10 can be stated as follows.

Theorem 4.8. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 ≥ 2 , and G be a 2-connected graph of order n , where k ≥ 0 , a 1 ≥ · · · ≥ a k ≥ 1 , b 1 ≥ b 2 , and n ≥ 4(2 h +1) 2 ( 2 h +1 h ) .

- n,h
- (a). If δ G ( ) ≥ h and k = 0 , then F ⊆ G , unless one of the following holds: (i). G ⊆ S + ;
- (ii). F = P 7 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 , where n is even;
- (b). If δ G ( ) ≥ h and k ≥ 1 , then F ⊆ G , unless one of the following holds:
- (iii). F = P 9 ⋃ P 3 and G ⊆ K 3 ∨ n -3 2 K 2 , where n is odd.
- (iv). G ⊆ S n,h ;
- (vi). F = P 6 ⋃ 2 P 3 and G ⊆ K 3 ∨ n -3 2 K 2 , where n is odd.
- (v). F = P 4 ⋃ 2 P 3 and G ⊆ K 2 ∨ n -2 2 K 2 , where n is even ;

Proof. Suppose F /notsubseteql G . If h = 2, then F = P 5 ⋃ P 3 . By Lemma 4.1 ( ii ), either G ⊆ S + n, 2 , G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 for n = 2 t -1. However, G is not 2-connected whenever G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 . Hence G ⊆ S + n, 2 . Next we assume that h ≥ 3. Let C l be the longest cycle in G . By Lemma 4.2, 2 h ≤ l ≤ 2 h +1. It is easy to see that Corollary 4.4 together with Lemma 4.6 implies that G ⊆ S + n,h , F = P 7 ⋃ P 3 and G ⊆ K 2 ∨ n -2 2 K 2 for even n , or F = P 9 ⋃ P 3 and G ⊆ K 3 ∨ n -3 2 K 2 for odd n .

(b). Suppose F /notsubseteql G . If h = 2, then F = P 2 ⋃ 2 P 3 . By Lemma 4.1 ( iii ), either G ⊆ S n, 2 , or G = L t, 2 for n = 2 t -1. However, if G = L t, 2 , then G is not 2-connected. Hence G ⊆ S n, 2 . Next we assume that h ≥ 3. Let C l be the longest cycle in G . By Lemma 4.2, 2 h ≤ l ≤ 2 h +1. It is easy to see that Corollary 4.5 together with Lemma 4.7 implies that G ⊆ S n,h , F = P 4 ⋃ 2 P 3 and G ⊆ K 2 ∨ n -2 2 K 2 for even n , or F = P 6 ⋃ 2 P 3 and G ⊆ K 3 ∨ n -3 2 K 2 for odd n . Thus the assertion holds. /square

We will use the next two lemmas in Theorem 1.11.

Lemma 4.9. Let F = ⋃ 2 i =1 P 2 b i +1 , h = ∑ 2 i =1 b i -1 ≥ 3 , and G be a connected graph of order n with at least one cut vertex, where b 1 ≥ b 2 ≥ 1 and n ≥ 2 h +4 . If δ G ( ) ≥ h , then F ⊆ G , unless one of the following holds:

- (i) F = P 2 b 1 +1 ⋃ P 2 b 1 -1 and G = L t,h , where n = th +1 ;

(ii) F = 2 P 2 b 1 +1 and G = U 3 ,h , where n = 3 h +3 ;

(iii) F = 2 P 2 b 1 +1 and G ⊆ L t 1 ,t 2 ,h,h +1 , where n = t 1 h + t 2 ( h +1) + 1 ;

(iv) F = 2 P 2 b 1 +1 and G ⊆ F t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +1)( h +1) + 1 ;

(v) F = 2 P 2 b 1 +1 and G ⊆ T t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +2)( h +1) + 1 .

Proof. Suppose F /notsubseteql G . Since ∑ k i =1 2 a i + ∑ 2 i =1 (2 b i +1) = 2 h +4, we have P 2 h +4 /notsubseteql G . Note that h + 2 ≥ 2 b 2 +1 and 2 h +1 ≥ 2 b 1 +1. We have P h +2 ⋃ P 2 h +1 /notsubseteql G . Note that h + 1 ≥ 2 b 2 + 1 and 2 h + 1 ≥ 2 b 1 + 1 for b 1 ≥ b 2 + 1. We also have P h +1 ⋃ P 2 h +1 /notsubseteql G for b 1 ≥ b 2 +1. Note that h ≥ 2 b 2 +1 and 2 h +1 ≥ 2 b 1 +1 for b 1 ≥ b 2 +2. Moreover, P h ⋃ P 2 h +1 /notsubseteql G for b 1 ≥ b 2 +2.

Since G has at least one cut vertex, it has at least two end blocks. Furthermore, since δ G ( ) ≥ h , it follows that | V ( B ) | ≥ h + 1 for every end block B . Choose two end blocks B 1 and B 2 of G such that p B , B ( 1 2 ) is as large as possible, where p B , B ( 1 2 ) is the order of a longest path between the cut vertex u 1 of G in V ( B 1 ) and the cut vertex u 2 of G in V ( B 2 ). Lemma 2.1 together with P 2 h +4 /notsubseteql G implies that p B , B ( 1 2 ) ≤ 3. We assume without loss of generality that | V ( B 1 ) | ≤ | V ( B 2 ) . | We consider the following three cases.

Case 1 : p B , B ( 1 2 ) = 1. This implies that all blocks in G are end blocks and they share a common cut vertex of G . We first prove the following Claim.

Claim: G has at least three end blocks.

Suppose that G has exactly two end blocks B 1 and B 2 . Since n ≥ 2 h +4 and | V ( B 1 ) | ≤ | V ( B 2 ) , | if | V ( B 1 ) | ≥ h + 2 then | V ( B 2 ) | ≥ h + 3. By Lemma 2.1, P 2 h +4 ⊆ G , a contradiction. Hence we assume that | V ( B 1 ) | = h + 1 and thus | V ( B 2 ) | ≥ h + 4. We claim h = 3 (Otherwise h ≥ 4. By Lemma 2.1, B 2 has a path P min 2 { h,h +4 } with an end vertex u 2 . Since min { 2 h, h + 4 } ≥ h + 4, we have P 2 h +4 ⊆ G , a contradiction.). It follows that either F = P 7 ⋃ P 3 or F = 2 P 5 . Furthermore, by Lemmas 2.1 and 2.7 ( iii ), F ⊆ G , a contradiction. This completes the claim.

By Claim above, G has at least three end blocks. Since P h +2 ⋃ P 2 h +1 /notsubseteql G , all blocks have order at most h + 2 and P h ⋃ P 2 h +1 ⊆ G . Note P h ⋃ P 2 h +1 /notsubseteql G

for b 1 ≥ b 2 + 2. Hence b 2 ≤ b 1 ≤ b 2 + 1. If b 1 = b 2 , then F = 2 P 2 b 1 +1 and G ⊆ L t 1 ,t 2 ,h,h +1 , where n = t 1 h + t 2 ( h +1) + 1. Next we assume that b 1 = b 2 +1. Note P h +1 ⋃ P 2 h +1 /notsubseteql G for b 1 = b 2 +1. It follows that all blocks have order h +1. Thus F = P 2 b 1 +1 ⋃ P 2 b 1 -1 and G = L t,h , where n = th +1.

Case 2 : p B , B ( 1 2 ) = 2. This implies that all blocks in G are end blocks. Lemma 2.1 together with P 2 h +4 /notsubseteql G implies that | V ( B 1 ) | = h + 1 and h + 1 ≤ | V ( B 2 ) | ≤ h +2. Thus G is a graph obtained by adding an edge to the centers of L t 1 ,t 2 ,h,h +1 and L t 3 ,t 4 ,h,h +1 , where n = ( t 1 + t 3 ) h +( t 2 + t 4 )( h +1)+2, t 1 + t 2 ≥ 1, and t 3 + t 4 ≥ 1. Furthermore, since P h +2 ⋃ P 2 h +1 /notsubseteql G , either t 1 + t 2 = 1 or t 3 + t 4 = 1. We assume without loss of generality that t 1 + t 2 = 1. Since n ≥ 2 h +4, it follows that t 3 + t 4 ≥ 2. So P h +1 ⋃ P 2 h +1 ⊆ G . Note P h +1 ⋃ P 2 h +1 /notsubseteql G for b 1 ≥ b 2 + 1. Then b 1 = b 2 and thus F = 2 P 2 b 1 . Moreover, since P h +2 ⋃ P 2 h +1 /notsubseteql G , it follows that t 2 = 0 and thus t 1 = 1. Therefore, F = 2 P 2 b 1 +1 and G ⊆ F t 3 ,t 4 ,h,h +1 , where n = t 3 h +( t 4 +1)( h +1) + 1.

Case 3 : p B , B ( 1 2 ) = 3. Lemma 2.1 together with P 2 h +4 /notsubseteql G implies that | V ( B 1 ) | = | V ( B 2 ) | = h + 1. Note P h +2 ⋃ P 2 h +1 /notsubseteql G . The end block B i is the unique end block with u i ∈ V ( B i ) for 1 ≤ i ≤ 2. Denote u uu 1 2 by the path between u 1 and u 2 . Since δ G ( ) ≥ 3, there exists an end block of order at least h +1 with the vertex u . Hence P h +1 ⋃ P 2 h +1 ⊆ G . Note P h +1 ⋃ P 2 h +1 /notsubseteql G for b 1 ≥ b 2 +1. So b 1 = b 2 and thus F = 2 P 2 b 1 . Furthermore, since p B , B ( 1 2 ) = 3, there is exactly one path P 3 between u 1 and u 2 . Since P h +2 ⋃ P 2 h +1 /notsubseteql G , if u u 1 2 ∈ E G ( ) then there is exactly one end block with the vertex u and it has order h +1. Hence F = 2 P 2 b 1 +1 and G = U 3 ,h , where n = 3 h + 3. Next we assume u u 1 2 / E G ∈ ( ). Obviously, u u 1 and u u 2 are both cut edges of G . Since P h +2 ⋃ P 2 h +1 /notsubseteql G , all blocks that contains u have order at most h + 2. Therefore F = 2 P 2 b 1 +1 and G ⊆ T t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +2)( h +1) + 1.

Thus the assertion holds. /square

Lemma 4.10. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 ≥ 2 , and G be a connected graph of order n with at least one cut vertex, where k ≥ 1 , a 1 ≥ · · · ≥ a k ≥ 1 , b 1 ≥ b 2 ≥ 3 , and n ≥ 2 h +4 . If δ G ( ) ≥ h , then F ⊆ G , unless F = P 2 ⋃ 2 P 2 b 1 +1 and G = L t,h , where n = th +1 .

Proof. Suppose F /notsubseteql G . If h = 2, then F = P 2 ⋃ 2 P 3 . By Lemma 4.1 ( ii ), we have G ⊆ S + n, 2 , G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 for n = 2 t + 1. However, G is 2-connected whenever G ⊆ S + n, 2 and F ⊆ G whenever G ⊆ H 1 n or G ⊆ H 2 n . Hence G = L t, 2 , where n = 2 t + 1. Next we assume that h ≥ 3. Let F ′ = ⋃ 2 i =1 P 2 b ′ i +1 , where b ′ 1 = ∑ k i =1 a i + b 1 and b ′ 2 = b 2 . We have F ′ /notsubseteql G . Note that k ≥ 1 and b 1 ≥ b 2 . It follows that b ′ 1 &gt; b ′ 2 . By Lemma 4.9, G = L t,h , where n = th + 1 and F ′ = P 2 b ′ 1 +1 ⋃ P 2 b ′ 1 -1 . Moreover, since F ′ = P 2 b ′ 1 +1 ⋃ P 2 b ′ 1 -1 , it follows that k = 1, a 1 = 1, and b 1 = b 2 . Hence F = P 2 ⋃ 2 P 2 b 1 +1 . Thus the assertion holds. /square

Theorem 1.11 can be stated as follows.

Theorem 4.11. Let F = ( ⋃ k i =1 P 2 a i ) ⋃ ⋃ ( 2 i =1 P 2 b i +1 ) , h = ∑ k i =1 a i + ∑ 2 i =1 b i -1 , and G be a connected graph of order n with at least one cut vertex, where a 1 ≥ · · · ≥ a k ≥ 1 , b 1 ≥ b 2 ≥ 1 , k ≥ 0 , and n ≥ 2 h +4 .

(a). If δ G ( ) ≥ h ≥ 1 and k = 0 , then F ⊆ G , unless one of the following holds: (i) F = P 5 ⋃ P 3 and either G ⊆ H 1 n or G ⊆ H 2 n ;

(ii) F = P 2 b 1 +1 ⋃ P 2 b 1 - 1 and G = L t,h , where n = th +1 ; (iii) F = 2 P 2 b 1 +1 and G = U 3 ,h , where n = 3 h +3 ; (iv) F = 2 P 2 b 1 +1 and G ⊆ L t 1 ,t 2 ,h,h +1 , where n = t 1 h + t 2 ( h +1) + 1 ; (v) F = 2 P 2 b 1 +1 and G ⊆ F t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +1)( h +1) + 1 ; (vi) F = 2 P 2 b 1 +1 and G ⊆ T t 1 ,t 2 ,h,h +1 , where n = t 1 h +( t 2 +2)( h +1) + 1 .

(b). If δ G ( ) ≥ h ≥ 2 an k ≥ 1 , then F ⊆ G , unless F = P 2 ⋃ 2 P 2 b 1 +1 and G = L t,h , where n = th +1 .

Proof. (a). Suppose F /notsubseteql G . If h = 1, then F = 2 P 3 . By Lemma 4.6 ( ), either i G = U 3 1 , or G ⊆ L t 1 ,t 2 , 1 2 , for n = t 1 +2 t 2 +1. Next we assume that h = 2. It follows that F = P 5 ⋃ P 3 . By Lemma 4.6 ( ii ), G ⊆ S + n, 2 , G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 for n = 2 t + 1. However, G is 2-connected whenever G ⊆ S + n, 2 . Hence G ⊆ H 1 n , G ⊆ H 2 n , or G = L t, 2 for n = 2 t +1. Finally we assume that h ≥ 3. The assertion follows by Lemma 4.9.

- (b). The assertion follows by Lemma 4.10. /square

## Acknowledgements:

The authors would like to thank the anonymous referee for many helpful and constructive suggestions to an earlier version of this paper, which results in an great improvement.

## References

- [1] B. Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat. Lapok 13 (1962) 95-107.
- [2] A.A. Ali and W. Staton, On extremal graphs with no long paths, Electron. J. Combin. 3 (1996), Research Paper 20, approx. 4 pp.
- [3] N. Bushaw and N. Kettle, Tur´n numbers of multiple paths and equibipartite a forests, Combin. Probab. Comput. 20 (2011) 837-853.
- [4] M.-Z. Chen and X.-D. Zhang, The number of edges, spectral radius and Hamilton-connectedness of graphs, J. Comb. Optim. 35 (2018) 1104-1127.
- [5] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math Soc. 2 (1952) 69-81.
- [6] P. Erd˝s and T. Gallai, On maximal paths and circuits of graphs, Acta Math. o Acad. Sci. Hungar. 10 (1959) 337-356.
- [7] Z. F¨redi, A. Kostochka, J. Verstra¨te, Stability in the Erd˝s-Gallai Theorems u e o on cycles and paths, J. Combin. Theory Ser. B, 121 (2016) 197-228.
- [8] B. Lidick´, y H. Liu, C. Palmer, On the Tur´n number of forests, Electron. J. a Combin. 20 (2) (2013) Paper 62, 13 pp.
- [9] V. Nikiforov and X.Y. Yuan, Maxima of the Q -index: graphs without long paths, Electron. J. Linear Algebra 27 (2014) 504-514.
- [10] D.B. West, Introduction to Graph Theory, Prentice-Hall, London, 2001.

- [11] L.-T. Yuan and X.-D Zhang, The Tur´ an number of disjoint copies of path, Discrete Math. 340 (2) (2017) 132-139.
Ming-Zhu Chen Xiao-Dong Zhang
Erdos-Gallai Stability Theorem for Linear Forests
The Erd\H{o}s-Gallai Theorem states that every graph of average degree more
than $l-2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain
a stability version of the Erd\H{o}s-Gallai Theorem in terms of minimum degree.
Let $G$ be a connected graph of order $n$ and
$F=(\bigcup_{i=1}^kP_{2a_i})\bigcup(\bigcup_{i=1}^lP_{2b_i+1})$ be $k+l$
disjoint paths of order $2a_1, \ldots, 2a_{k}, 2b_1+1, \ldots, 2b_l+1,$
respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\geq 2$. If the minimum
degree $\delta(G)\ge \sum_{i=1}^ka_i+\sum_{i=1}^lb_i-1$, then $F\subseteq G$
except several classes of graphs for sufficiently large $n$, which extends and
strengths the results of Ali and Staton for an even path and Yuan and Nikiforov
for an odd path.