An Extension of the Win Theorem:Counting the Number of Maximum Independent Sets?

Wanpeng LEILiming XIONGJunfeng DUJun YIN

AbstractWin proved a well-known result that the graph G of connectivity κ(G)with α(G)≤ κ(G)+k?1(k≥ 2)has a spanning k-ended tree,i.e.,a spanning tree with at most k leaves.In this paper,the authors extended the Win theorem in case when κ(G)=1 to the following:Let G be a simple connected graph of order large enough such that α(G)≤ k+1(k ≥ 3)and such that the number of maximum independent sets of cardinality k+1 is at most n?2k?2.Then G has a spanning k-ended tree.

Keywords k-ended tree,Connectivity,Maximum independent set

1 Introduction

A graph is traceable if it contains a Hamilton path,and hamiltonian if it contains a Hamilton cycle.In 1972,Chv′atal and Erd?os gave the following well-known sufficient condition for a graph to be traceable.Given a graph G,let κ(G)and α(G)denote the connectivity and the independence number of G,respectively.

Theorem 1.1 (see[6])If G is a graph on at least 3 vertices such that α(G)≤ κ(G)+1,then G is traceable.

Theorem 1.1 has been extended in many different directions(see[1–2,7,9–11]).For the recent results,see[4,8,12].

A Hamiltonian path is a spanning tree having exactly two leaves.From this point of view,some sufficient conditions for a graph to be traceable are modified to those for a spanning tree having at most k leaves.A tree having at most k leaves is called a k-ended tree,and we now turn our attention to spanning k-ended trees.It is clear that if s≤t then a spanning s-ended tree is also a spanning t-ended tree.Theorem 1.1 says that every graph G satisfying α(G)≤ κ(G)+1 is traceable.Las Vergnas conjectured the following theorem,which is a generalization of Theorem 1.1.This conjecture was proved by Win,who introduced a new proof technique called a k-ended system.

Theorem 1.2 (see[14])Let k≥2 be an integer and G be a connected simple graph.If α(G)≤ κ(G)+k?1,then G has a spanning k-ended tree.

Let m(H)denote the number of maximum independent sets of H for a subgraph H?G.In[5],Chen et al.proved that it does not change the traceability of those graphs G with a slight larger independence number(i.e.,α(G)≤ κ(G)+2)when we bound m(G).The complete graph with s vertices is denoted by Ksand its complement is denoted by,i.e.,sK1.By starting with a disjoint union of two graphs G and H and adding edges joining every vertex of G to every vertex of H,one obtains the join of G and H,denote by G∨H.

Theorem 1.3 (see[5])Let G be a connected graph of order n ≥ 2κ2(G)such that α(G)≤κ(G)+2,κ(G)= κ≥ 1 and m(G)≤ n?2κ(G)?1.Then either G is traceable or a subgraph of Kκ∨ ((κK1)∪ Kn?2κ).

In this paper,we extend Theorem 1.2 in the case when κ(G)=1 by the following direction.

Theorem 1.4 Let k≥ 3 and G be a connect graph of order n ≥ 2k+2 such that α(G)≤ 1+k and m(G)≤n?2k?2.Then G has a spanning k-ended tree.

2 Notation and Terminology

For graph-theoretic notation not explained in this paper,we refer the reader to[13].Let G=(V(G),E(G))be a graph with vertex set V(G)and edge set E(G).We denote by N(v)the neighborhood of vertex v in G.For a nonempty subset X of V(G),we writeFor S?V(G),we denote by G[S]the subgraph of G induced by S.Let H1and H2be two vertex disjoint subgraphs of G,x,y∈V(G),and P is a path of G.A path xPy in G with end vertices x and y is called a path from H1to H2if V(xPy)∩V(H1)={x}and V(xPy)∩V(H2)={y}.A path from{x}to a vertex set U is also called an(x,U)-path.A subgraph F of G is called an(x,U)-fan of width k if F is a union of(x,U)-paths P1,P2,···,Pk,where V(Pi)∩V(Pj)={x}for i ≠j.Let G0be a subgraph of G.For the convenience,if G[{x}∪V(G0)]has a spanning path one of whose end vertices is x,then we denote by xG0(G0x,respectively)the spanning path of G[{x}∪V(G0)],which starts at x(terminates at x,respectively).If G[V(G0)∪{x,y}]has a spanning path,then we denote by xG0y the spanning path of G[V(G0)∪{x,y}],which starts at x and terminates at y.Let G1and G2be two subgraphs of G.If G[V(G1)∪{x}∪V(G2)]has a spanning path,then we denote by G1xG2the spanning path of G[V(G1)∪{x}∪V(G2)].

We now introduce the concept of a k-ended system in order to prove Theorem 1.4.We denote the set of all simple graph by G.Define a function f:G→{0,1,2}as follows:For each element X of G,

Let S be a set of vertex-disjoint subgraphs X of G with f(X)≥1,and

Then

Moreover,V(SP)and V(SC)can be defined analogously,and|S|,|SP|,|SC|denote the number of elements in S,SPand SC,respectively.For each path P∈SP,let vL(P)and vR(P)denote the two end-vertices of P.For each element C∈SC,let vCbe an arbitrarily chosen vertex of C.Once we choose a vertex vC,each C corresponds the unique vertex vC.Then define

Then S is called a k-ended system if.If V(S)=V(G),then S is called a spanning k-ended system of G.

For any P ∈ SP,we orient P from vL(P)to vR(P),sayfor the oriented path(from vR(P)to vL(P),say,respectively).With a given orientationand for every vertex x of P,we will denote the first,second and ith predecessor(successor,respectively)of x as x?,x??and xi?(x+,x++,and xi+,respectively).If x=vR(P)(x=vL(P),respectively),we have only predecessor of vR(P)(successor of vL(P),respectively).Given x and y on P,a section P(x,y)is a path x+x2+x3+···xs+(=y?)of consecutive vertices of P,and a section P[x,y]is a path xx+x2+···xs+(=y)of consecutive vertices of P.The section P[x,y]is trivial if x=y.

For each element C ∈ SCand|V(C)| ≥ 3,with a given orientationand for every vertex v of C,let v+and v?denote the successor and the predecessor of v,respectively.

The following lemma shows why a k-ended system is important for spanning k-ended trees.

Lemma 2.1 (see[14])Let k≥3 be an integer,and G be a connected simple graph.If G has a spanning k-ended system,then G has a spanning k-ended tree.

We call a k-ended system S of G a maximal k-ended system if there exists no k-ended system S′in G such that V(S)? V(S′).The following lemma expresses some nice properties of k-ended systems.Note that we say that two distinct elements of S are connected by a path in G?V(S)if there exists a path in G whose end-vertices are in S and whose inner vertices are all contained in V(G)V(S),where a path may has no inner vertex.

Lemma 2.2 (see[3])Let k≥3 be an integer,and G be a connected simple graph.Suppose that G has no spanning k-ended system,and let S be a maximal k-ended system of G such that|SP|is maximum subject to the maximality of V(S).Then the following statements hold.

(i)No two elements of SCare connected by a path whose inner vertices are in V(G)V(S).

(ii)No element of SCis connected to an end-vertex of an element of SPby a path whose inner vertices are in V(G)V(S).

(iii)No end-vertex of an element of SPis connected to an end-vertex of another element of SPby a path whose inner vertices are in V(G)V(S).

(iv)No vertex u in V(G)V(S)is connected to two distinct elements of SCby two internally disjoint paths Q1and Q2in G?V(S)such that V(Q1)∩V(Q2)={u}.

3 Preparatory Works for Proving Theorem 1.4

In the following section,for the convenience,we assume the following:Let k≥3 be an integer,and G be a simple connected graph such that α(G)=1+k.Suppose that G has no spanning k-ended system,and let S be a maximal k-ended system of G such that

(I)|V(S)|is maximized.

(II)|SP|is maximized subject to(I).

(III)|V(SP)|is maximized subject to(I)and(II).

Then S is a set of subgraphs of G satisfying the hypothesis of Lemma 2.2.Let H=G?V(S).Then|V(H)|≥1.

For the convenience,we assume that x ∈ V(P).For any P ∈ SP,let(x,P)=vR(P)if x=vR(P),and(x,P)=xvR(P)if x+=vR(P).In the case when x ≠vR(P)and x+≠vR(P),we also let(x,P)=xvR(P)x if xvR(P) ∈ E(G).Otherwise,we do not define(x,P).Let(x,P)=vL(P)if x=vL(P),and(x,P)=xvL(P)if x?=vL(P).In the case when x ≠vL(P)and x?≠vL(P),we also let(x,P)=xvL(P)x if xvL(P)∈E(G).Otherwise,we do not define(x,P).Then,f((x,P))=1(f((x,P))=1,respectively).Let G0be a subgraph of G,C(G0)is called a spanning subgraph of G0such that f(C(G0))=1.

Lemma 3.1 G has no k′-ended system T such that V(T)? V(S)and k′

Lemma 3.2 Suppose that there exists a path L from v∈ V(H)to S such that V(L)∩V(S)={x}and x∈V(P)for some P ∈SP.Then N(x+)∩(End(SP){vR(P)})=?.

Proof By contradiction,suppose that N(x+)∩(End(SP){vR(P)})≠ ?,say y∈ N(x+)∩(End(SP){vR(P)}).It is easy to check that x/∈{vL(P),vR(P)}.Let N(x)∩V(L)={v′}.Then,we distinguish the following two cases to obtain a contradiction:

(1)Suppose that y∈End(SP){vL(P),vR(P)}.Without loss of generality,assume that y=vL(P′)for P′∈SP{P}.Thenandcover V(P′)∪ V(P)∪ {v′},contradicting(I).

(2)Suppose that y=vL(P).Thenin G covers V(P)∪{v′},contradicting(I).

This contradiction proves Lemma 3.2.

Lemma 3.3 For any v∈V(H),G has no(v,V(S))-fan of width 2.

Proof By contradiction,suppose that there exists a(v,V(S))-fan{L1,L2}of width 2 for some v∈ V(H).Let V(Li)∩V(S)={ui}for i∈ {1,2}.Denote U={u1,u2}.If U∩V(SC)≠ ?,then there exists at least one vertex y∈U∩V(SC).Without loss of generality,we assume that y=u1.By Lemma 2.2(iv),|{C:C∈SCand U∩V(C)≠?}|=1,say C1∈SCand U ∩V(C1)≠ ?.For each isolated vertex{x}(say)of SC,N(x)∩(V(G)V(S))= ?.Thus no isolated vertex of SCis adjacent to V(G)V(S).Then|V(C1)|≥2.If|V(C1)|=2,then we assume that C1contains a vertex of U,say vC1.Let,where vC1∈End(SC).Obviouslyis not contained in U.Denote

We distinguish the following three cases to prove that Y includes an independent set of G with size at least k+2.

Case 1|U∩V(SP)|=|U∩V(SC)|=1.

Suppose that u1∈ V(C1)and u2∈ V(P)for some P ∈ SP.By Lemma 2.2(iv),is an independent set of G.Letand.Then,we distinguish the following four cases to prove that Y{vC1}is an independent set of G with size k+2:

These contradictions show that Y{vC1}is an independent set of G with size k+2.

Case 2 U?V(SC).

Case 3 U∩V(SC)=?,i.e.,U?V(SP).

Suppose first that End(S)∩ U+= ?.Then|Y|=k+3.By the assumption of this case,End(S) ∪ {v}is an independent set of G.Letand Q5=.We shall show the following two claims.

Claim 1 G[Y]is triangle-free.

Proof We shall prove that U+is an independent set of G.

Claim 2 Y does not contain four distinct vertices y1,y2,y3,y4such that{y1y2,y3y4}?E(G).

Proof By contradiction,suppose that Y contains four distinct vertices y1,y2,y3,y4such that{y1y2,y3y4}?E(G).Without loss of generality,assumeV(P′),and if they are in the same path P(say),then P[vL(P),u1]? P[vL(P),u2](say).Then,we distinguish the following three cases to obtain a contradiction.

(1)Suppose that y1=vC∈ End(SC),y3=vC′ ∈ End(SC)and vC≠vC′.If P ≠P′,then Q5,andcover V(P)∪V(P′)∪V(C)∪V(C′)∪{v},contradicting(I).If P=P′,thencover V(P)∪V(C)∪V(C′)∪{v},contradicting(I).

(2)Suppose that y1=vC∈ End(SC)and y3=vR(P′).If P ≠P′,then Q5,andcover V(P)∪V(P′)∪V(C)∪{v},contradicting(I).If P=P′,thenQ3cover V(P)∪V(C)∪{v},contradicting(I).

(3)Suppose that y1=vR(P)and y3=vR(P′),where P ≠P′.Then Q5,andcover V(P)∪ V(P′)∪ {v},contradicting(I).

This contradiction proves Claim 2.

By Claims 1–2,Y includes an independent set of G with size at least k+2.

Next,suppose that End(S)∩U+≠?.Then,there exists a path P ∈SPsuch that vR(P)=.Without loss of generality,say.If there exists another path Q∈SP{P}such that vR(Q)=u+2,then Q5,vR(P),vR(Q)cover V(P)∪V(Q)∪{v},contradicting(I).Thus U+∩End(S)={vR(P)}for some P∈SP,and|Y|=k+2.we will show that Y is an independent set of G with size k+2.

Assume that vC∈ End(SC)and u+2∈ V(P′)are adjacent in G.If P ≠P′,then Q5,cover V(P)∪V(P′)∪V(C)∪{v},contradicting(I).If P=P′,thenvR(P)cover V(P)∪V(C)∪{v},contradicting(I).

Assume that vR(P′)and∈ V(P′)are adjacent in G,where P ≠P′.ThenvR(P)cover V(P)∪V(P′)∪{v},contradicting(I).

These contradictions shows that Y is an independent set of G with size k+2.

In all cases,Y includes an independent set of G with size at least k+2,contradicting α(G)=k+1.This contradiction shows that Lemma 3.3 holds.

Let w be a vertex in V(G)V(S).Since G is connected,by Lemma 3.3,there exists exactly one(w,V(S))-path L such that V(L)∩V(S)={μw}.Then w is connected to μwby the path L.

Lemma 3.4 N(v)∩End(SP)=?for any v∈V(H).

Cμwalways means the vertex μw∈ V(Cμw)where Cμw∈ SC.Then|V(Cμw)|≥ 2,since no isolated vertex of SCis adjacent to V(G)V(S).If|V(Cμw)|=2,saywithout loss of generality,then we assume that μw=vCμw.It means that vCμw∈ End(SC).

Denote

Pμwalways means that the vertex μw∈ V(Pμw),where Pμw∈ SP.Let

Lemma 3.5 X is an independent set of G with size k+1.

Proof By Lemma 2.2,End(S)is an independent set of G.Sinceμw∈V(SP)or V(SC),by Lemmas 2.2 and 3.4,X is an independent set of G with size k+1.

By Lemma 3.5,we have

Otherwise,there exists a vertex v0∈V(G)X such that X∪{v0}is an independent set of cardinality k+2,contradicting α(G)=k+1.

Lemma 3.6 Let S?V(G)such that S∩X has exactly one vertex,say z,i.e,S∩X={z}.If N(x)∩X={z}for any x∈S{z},then G[S]is a clique.

Proof By contradiction,suppose that x1x2/∈E(G)for some pair of vertices x1,x2∈S with x1≠x2,then(X{z)})∪{x1,x2}is an independent set of G with size k+2,contradicting α(G)=1+k.Hence,G[S]is a clique.

Denote

Lemma 3.7 G[V(C)]is a clique for each C∈

Proof Since G[V(C)]is connected,it suffices to consider the case when|V(C)|≥3.Note that V(C)∩X={vC}.By Lemma 2.2(i)–(ii),N(x)∩(X{vC})= ?for each vertex x∈ V(C){vC}.Note that N(x)∩X ≠ ?.Therefore N(x)∩X={vC}.Let S=V(C).Then,by Lemma 3.6,G[V(C)]is a clique.

Lemma 3.8 For any P∈SP,there is no pair of adjacent vertices x,y in P such that N(x)∩V()≠?and N(y)∩V()≠?.

ProofBy contradiction,suppose that there exists a pair of vertices x0,y0in P∈SPsuch that x0y0∈E(P),N(x0)∩V()≠?and N(y0)∩V()≠?.By Lemma 2.2(i)–(ii),x0/∈{vL(P),vR(P)}and y0/∈{vL(P),vR(P)}.Without loss of generality,assume that y0=.Suppose that N(x0)∩V()={x′}and N(y0)∩V()={y′}.We distinguish the following two cases to obtain a contradiction.

(1)Suppose that{x′,y′}?V(C)with C∈.If either|V(C)|=1 or x′≠y′,then by Lemma 3.7,in G covers V(P) ∪ V(C),contradicting Lemma 3.1.If x′=y′and|V(C)|>1,thenandin G cover V(P)∪V(C),satisfying(I),(II)but not(III),a contradiction.

(2)Suppose that x′∈V(C)and y′∈V(C′)such that{C,C′}?and V(C)∩V(C′)=?.Then,andin G cover V(P) ∪ V(C) ∪ V(C′),satisfying(I)but not(II),a contradiction.

This contradiction proves Lemma 3.8.

Denote

Lemma 3.9 Let P∈SP.Then the following three statements hold.

(1)If x∈TP,1∪TP,2∪{μw},then either N(x+)∩X?(End()∪{vR(P)})or x+=vR(P).

(2)If x∈TP,2,then either N(x+)∩X={vR(P)}or x+=vR(P).

(3)If x=μw,then either N(x?)∩X?(End()∪{vL(P)})or x?=vL(P).

Proof First,we will prove Lemma 3.9(1).We denote set End()∪{vR(P)}by B1.If x+≠vR(P),then we will show that N(x+)∩X?B1.Since B1?X,we denote X?B1by B2.By the assumption of this case,w/∈N(x+)∩X.

Suppose that x= μw.Then by Lemma 3.2,N(x+)∩(End(SP){vR(P)})= ?.Combining this with(3.1),N(x+)∩B2=?.Hence,N(x+)∩X ? B1.By symmetry,Lemma 3.9(3)holds.

Suppose that x∈ TP,1∪TP,2.Then,suppose that there exists a vertex x′∈ N(x+)∩B2.We distinguish the following three cases to obtain a contradiction by the definition of X.

(1)Suppose that x′∈ End(SP){vL(P),vR(P)}.Without loss of generality,assume that x′=vL(P′)for P′∈SP{P}.If x∈TP,1,thenandin G cover V(P′)∪V(P),contradicting Lemma 3.1.If x∈TP,2,say vC∈N(x)∩V(),thenandin G cover V(P′)∪V(P)∪V(C),contradicting Lemma 3.1.

(2)Suppose that x′=vL(P).If x∈TP,2,say vC∈N(x)∩V(),thenvR(P)in G covers V(P)∪V(C),contradicting Lemma 3.1.

(3)Suppose that x′=.Then,by Lemma 3.5 and(3.1), μw∈ V(SC).If x ∈ TP,1,thenand(x,P)in G cover V(P)∪V(Cμw)∪{w},contradicting(I).If x∈TP,2,say vC∈N(x)∩V(),thenandin G cover V(P)∪V(C)∪V(Cμw)∪{w},contradicting(I).

This contradiction proves that N(x+)∩B2= ?.Hence,N(x+)∩X ? B1.Lemma 3.9(1)is proved.

If x∈TP,2then by Lemma 3.9(1),N(x+)∩X?(End()∪{vR(P)})or x+=vR(P).By Lemma 3.8,N(x+)∩V()=?.Note that(3.2).Therefore Lemma 3.9(2)holds.

Lemma 3.10 Let P∈SPand y∈V(P)with yvR(P)∈E(G),|V(P[y,vR(P)])|≥3 andμw/∈V(P[y,vR(P)]).Then it holds that N(y+)∩X={vR(P)}.

Proof By contradiction,suppose that there exists at least one vertex x∈N(y+)∩X such that x ≠vR(P).By the definition of X,we distinguish the following four cases to obtain a contradiction.

(1)Suppose that x∈End(SC),say x=vC.Thenin G covers V(P)∪V(C),contradicting Lemma 3.1.

(2)Suppose that x=vL(P)∈End(SP).Thenin G covers V(P),contradicting Lemma 3.1.

(3)Suppose that x∈End(SP){vL(P),vR(P)}.Without loss of generality,assume that x=vL(P′)for P′∈ SP{P}.Thenin G covers V(P)∪V(P′),contradicting Lemma 3.1.

This contradiction shows that N(y+)∩X ?{vR(P)}.By(3.2),N(y+)∩X={vR(P)}.

Lemma 3.11 The following two statements hold.

(1)Let P∈SPand y∈V(P)with yvR(P)∈E(G)andμw/∈V(P[y,vR(P)]).Then it holds that G[V(P[y+,vR(P)])]is a clique.Furthermore,if N(y)∩X={vR(P)},then G[V(P[y,vR(P)])]is a clique.

(2)Let P∈SPand x∈V(P)with xvL(P)∈E(G)andμw/∈V(P[vL(P),x]).Then it holds that G[V(P[vL(P),x?])]is a clique.Furthermore,if N(x)∩ X={vL(P)},then G[V(P[vL(P),x])]is a clique.

Proof By symmetry,we may only prove that(1)is true.Since G[V(P[y+,vR(P)])]is connected,it suffices to consider the case when|V(P[y+,vR(P)])|≥ 3.Note that V(P[y+,vR(P)])∩X={vR(P)}.Let S=V(P[y+,vR(P)]).Then by Lemma 3.6,it suffices to prove the following statement

We repeatedly apply Lemma 3.10 to obtain(3.3).

Furthermore,we will prove that if N(y)∩X={vR(P)},then G[V(P[y,vR(P)])]is a clique.Since G[V(P[y,vR(P)])]is connected,it suffices to consider the case when|V(P[y,vR(P)])|≥ 3.Note that N(y)∩X={vR(P)}.Combining this with(3.3),we have N(x)∩X={vR(P)}for each vertex x∈V(P[y,vR(P))).Let S=V(P[y,vR(P)]).Then by Lemma 3.6,G[V(P[y,vR(P)])]is a clique.

Lemma 3.12 Let P∈SPand x∈V(P){vL(P),vR(P)}with N(x)∩End()≠?.Then the following two statements hold.

(1)Ifμw/∈V(P[x+,vR(P)]),then G[V(P[x+,vR(P)])]is a clique.

(2)Ifμw/∈V(P[vL(P),x?]),then G[V(P[vL(P),x?])]is a clique.

Proof By symmetry,we may only prove that G[V(P[x+,vR(P)])]is a clique.Since G[V(P[x+,vR(P)])]is connected,it suffices to consider the case when|V(P[x+,vR(P)])|≥3.By Lemma 3.9(2),N(x+)∩X={vR(P)}.By Lemma 3.11(1),G[V(P[x+,vR(P)])]is a clique.

Lemma 3.13 For any pair of paths P,P′∈ SP,suppose that there exist two vertices x∈V(P){vL(P),vR(P)}and y∈V(P′){vL(P′),vR(P′)}such that N(x)∩End(S′C)≠?,N(y)∩End()≠?andμw/∈(V(P){x})∪(V(P′){y}).Then any pair of vertices in V(P){x}and V(P′){y}respectively are not adjacent.

Proof By symmetry,we only prove that any pair of vertices in V(P[x+,vR(P)])and V(P′[y+,vR(P′)])are not adjacent.

By contradiction,suppose that there exists a pair of vertices x0∈V(P[x+,vR(P)]),y0∈V(P′[y+,vR(P′)])such that x0y0∈ E(G).By Lemma 3.12(1),both G[V(P[x+,vR(P)])]and G[V(P′[y+,vR(P′)])]are cliques.Let Q6=G[V(P′[y+,vR(P′)])]x0G[V(P[x+,vR(P)]{x0})]andTo obtain our contradiction,we consider the following two cases:

(2)Suppose that there exist two distinct vertices vC∈ V(C)and vC′∈ V(C′)such that vC∈N(x)∩End(SC)and vC′∈N(y)∩End(SC).By Lemma 3.12(1),Q6,andin G cover V(P)∪V(P′)∪V(C)∪V(C′),satisfying(I)but not(II),a contradiction.

This contradiction shows that any pair of vertices in V(P[x+,vR(P)])andare not adjacent.

Lemma 3.14 Let P∈SPand x∈V(P){vL(P),vR(P)}.Then the following two statements hold.

(1)Suppose thatμw/∈V(P[vL(P),x])and N(x)∩(End()∪{vL(P)})≠?.Then N(V(C))∩V(P[vL(P),x))=?for any C∈SC.

(2)Suppose thatμw/∈V(P[x,vR(P)])and N(x)∩(End()∪{vR(P)})≠?.Then N(V(C))∩V(P(x,vR(P)])=?for any C∈SC.

Proof By symmetry,we may only prove that(1)holds.By contradiction,suppose that there exists some element C0∈ SCsuch that N(C0)∩V(P[vL(P),x))≠ ?,say z∈ N(V(C0))∩V(P[vL(P),x)).By Lemma 2.2(ii),z/∈End(SP).If xvL(P)∈E(G)or N(x)∩End(SC)≠?,then by Lemmas 3.11(2)and 3.12(2),G[V(P[vL(P),x?])]is a clique.Suppose that z=x?.By Lemma 3.8,N(x)∩V()=?.Then,xvL(P)∈E(G).Hence,if z∈V(P(vL(P),x?]),then by Lemmas 3.11(2)and 3.12(2),in G covers V(P)∪V(C0),contradicting Lemma 3.1.This contradiction proves Lemma 3.14(1).

For any path P∈SP,we know vL(P)vR(P)/∈E(G)by Lemma 3.1.We may take the vertex xPof V(P)such that V(P[vL(P),])?N(vL(P))and xP/∈N(vL(P)).

?Suppose that N(xP)∩V()=?.Then by Lemma 3.9(1)and(3.2),f(P[xP,vR(P)]xP)=1.By the assumption of this case and Lemma 3.14,

Lemma 3.15(2)holds.

Next,we will prove Lemma 3.15(3).By Lemma 3.15(1)–(2),f(P[xP,vR(P)]xP)=1 orIf,then we are done.Otherwise,f(P[,vR(P)]≠1.Then we assume that f(P[xP,vR(P)]xP)=1.Since G[V(P[xP,vR(P)])]is connected,it suffices to consider the case when|V(P[xP,vR(P)])|≥2.By Lemma 3.11(1),is a clique.Then.Lemma 3.15(3)holds.

Lemma 3.16 For any pair of{P,P′} ? SP,suppose there exists a pair of subpath-andIfandThen any pair of vertices inandrespectively are not adjacent.

Proof By symmetry,we only prove that any pair of vertices in V(P[vL(P),x+])and V(P′(y,vR(P′)])are not adjacent.

By contradiction,suppose that there exists a pair of vertices x0∈V(P[vL(P),x+])and y0∈V(P′(y,vR(P′)])with x0y0∈ E(G).By Lemma 3.11(1)–(2),we may obtain that G[V(P[vL(P),x?])]and G[V(P′[y+,vR(P′)])]are cliques.To obtain our contradiction,we distinguish the following two cases:

(1)Suppose that x0=vL(P).Then by Lemma 3.11(1),in G covers V(P) ∪ V(P′),contradicting Lemma 3.1.

(2)Suppose that x0∈V(P(vL(P),x+]).Then by Lemma 3.11(1),we may obtain thatandin G cover V(P) ∪ V(P′),contradicting Lemma 3.1.

This contradiction proves Lemma 3.16.

4 Proof of Theorem 1.4

In this section,we present the proof of Theorem 1.4.

Let k≥ 3 and G be a graph of order n>2k+2 such that α(G)≤ k+1 and m(G)≤ n?2k?2.We assume on the contrary that G has no spanning k-ended tree.The assumption that G has no spanning k-ended tree and Theorem 1.2 imply the following two equations

and

Then G have no spanning k-ended system by Lemma 2.1.Choose a maximal k-ended system S of G satisfying(I)–(III).Let H=G ? V(S).Then|V(H)|≥ 1.

Fact 1 m(G)≥n?2k?1.

ProofBy symmetry,we only consider y′’s neighbourhood.Suppose thatTaking any,we know z/∈V()by Lemma 3.15(1)–(2).By Lemmas 3.15(1)–(2)and 3.16,z/∈V(P′)for any P′∈{P}.Hence,z∈V(P).We claim that z/∈V(P[vL(P),)).Suppose otherwise thatThen by Lemma 3.11(1)–in G covers V(P),contradicting Lemma 3.1.This contradiction shows that our claim hold.By our claim,ifthen

By(4.3),Claim 1(2)holds.Suppose that.Ifand.Then there exists at least one vertex,by Lemma 3.11(2),in G covers V(P)∪V(C),contradicting Lemma 3.1.This contradiction shows thatClaim 1(1)is proved.

Let A=A1∪A2.Then X∩A=?and X0∩A1=?.

Claim 2 ω(G0?A1)=|X0|and each component of G0?A1is a clique.

Hence,Z is a component of G0?A1.By Lemmas 3.7,3.11(1)–(2)and 3.12(1)–(2),G[V(Z)]is a clique.By the definition of G0,it is easy to check that|X0∩V(Z)|=1,then ω(G0?A1)=|X0|.

Combining this with(4.4),we have

Denote

By Lemma 2.2,we distinguish the following two cases to prove Fact 1.

Case 1 μw∈V(SC),i.e.,μw∈V(Cμw).

By the choice of S,|SP|≥ 1.By(3.1)and Lemma 3.5,X={,w} ∪ (End(S){μw})is an independent set of G with size k+1.

Claim 3 G[V(Cμw){μw}]is a clique.

ProofSince G[V(Cμw){μw}]is connected,it suffices to consider the case when|V(Cμw){μw}|≥3.For each vertex v∈V(Cμw){μw,},v/∈End(S){μw}by Lemma 2.2(i)–(ii).Hence,by the definition of X and(3.2),N(v)∩ X={μ+w}for each vertex v ∈ V(Cμw){μw,}.Note that(V(Cμw){μw})∩X={}.Let S=V(Cμw){μw}.By Lemma 3.6,G[V(Cμw){μw}]is a clique.

Claim 4 If N(V(P))∩V(Cμw)≠?for any P ∈SP,then N(V(P))∩V(Cμw)={μw}.

ProofBy contradiction,suppose that there exists some P∈SPsuch that N(V(P))∩V(Cμw)≠ ? and N(V(P))∩V(Cμw)≠{μw},say v′∈ N(V(P))∩V(Cμw)satisfying v′≠ μw.Then there exists a vertex z∈V(P)such that v′z∈E(G).By Lemma 2.2(ii),z/∈End(SP).Suppose that z ∈ V(P){vL(P),vR(P)}.Then,by Lemmas 3.11(1)–(2)and 3.15(1)–(2),there exists Q′∈ {P[vL(P),z?]vL(P),P[z+,vR(P)]z+}such that f(Q′)=1.By Claim 3,G[E(PQ′)]v′CμwμwLw and Q′in G cover V(P)∪ V(Cμw)∪ {w},contradicting(I).This contradiction shows that Claim 4 holds.

Claim 5 G[V(H)]is a clique.

Proof First,we will show that G[V(H)]is connected.

By contradiction,suppose that H has at least two components.Choose any vertex v such that w and v belong to different components of H.We claim that N(v)∩V(Cμw)≠ ?.Suppose otherwise that N(v)∩V(Cμw)=?.Then/∈E(G).By Lemma 3.4,N(v)∩End(SP)=?.Suppose that N(v)∩End()≠?,say vvC∈E(G)(vC≠vCμw).Then|V(C)|≥2.Otherwise,vCv∈SC,contradicting(I).By Lemma 3.3,/∈E(G).Combining this with Lemma 2.2(i)–(ii),{v,}∪(X{vC})is an independent set of G with cardinality k+2,contradicting(4.2).Hence,N(v)∩End()=?.Then N(v)∩X=?,contradicting(3.2).Hence,N(v)∩V(Cμw)≠?.

By our claim and Lemma 3.3,N(V(P))∩V(H)=?for any P∈SP.Since G is connected,there exists at least one path P ∈ SPsuch that N(V(P))∩V(Cμw)≠ ?.By the arbitrariness of vertex w and Claim 4,N(v)∩V(Cμw)={μw}.By Lemma 3.5,{v,w,}∪(End(S){μw})is an independent set of G with cardinality k+2,contradicting(4.2).This contradiction proves that G[V(H)]is connected.

Next,we will show that G[V(H)]is a clique.Since G[V(H)]is connected,it suffices to consider the case when|V(H)|≥3.Since G[V(H)]is connected,by Lemma 3.3,N(v)∩(V(S){μw})= ?for each vertex v∈ V(H){w}.Note that(3.2),therefore,N(v)∩X={w}for every vertex v∈V(H){w}.Note that V(H)∩X={w}.Let S=V(H),then by Lemma 3.6,G[V(H)]is a clique.

Since G is connected,by Lemma 3.3 and Claims 4–5,we have the following claim.

Claim 6 N(V(H))∩V(S)={μw}and N(V(S′))∩V(Cμw)={μw}.

By Claims 2–6,ω(G?A)=k+1 and each component of G?A is a clique.

In this case,n0=n?|V(Cμw)|?|V(H)|and k0=k?1.Then,

which proves Fact 1 in this case.

Case 2 μw∈V(SP),i.e.,μw∈V(Pμw).

By(3.1)and Lemma 3.5,X=End(S)∪{w}is an independent set of G with size k+1.

Claim 7 G[V(H)]is a clique.

ProofIt suffices to consider the case when|V(H)|≥2.By(3.2),N(v)∩X ≠?for each vertex v∈V(H){w}.Suppose that there exists a vertex x∈N(v)∩X such that x ≠w.We claim that x/∈End(SC).Otherwise suppose that x∈End(SC),say x=vC.Then|V(C)|≥2.Otherwise,xv∈SC,contradicting(I).By Lemma 3.5,{v,}∪(End(S){vC})is an independent set of G with size k+1.By Lemma 3.3,N(w)∩(V(S){μw})= ?.Hence,{w,v,}∪(End(S){vC})would have an independent set of cardinality k+2,contradicting(4.2).This contradiction shows that our claim holds.

By Lemma 3.4 and our claim,N(v)∩X ?{w}.Note that(3.2),therefore,N(v)∩X={w}for each vertex v∈V(H){w}.Let S=V(H).Then by Lemma 3.6,G[V(H)]is a clique.

Claim 8 The following two statements hold:

Proof By symmetry,we may only prove thatis a clique.Sinceis connected,it suffices to consider the case when.By Lemma 3.9(1)and(3.2),.Then by Lemmas 3.11(1)and 3.12(1),is a clique.

Since G is connected,by Lemma 3.3 and Claim 7,we have the following claim.

Claim 9 N(V(H))∩V(S)={μw}.

By Claim 9,μwis the unique vertexμ(say)for any w∈V(H).Then denote

Claim 10 xy ?E(G)for any pair of vertices x∈B1and y∈B2.

Proof By contradiction,suppose that there exists a pair of vertices x0∈B1and y0∈B2such that x0y0∈E(G).To obtain our contradiction,we distinguish the following three cases.

(1)Suppose that N(μ?)∩ End(SC)≠ ?,say vC∈ (N(μ?)∩ End(SC)),and N(μ+)∩End(SC)≠ ?,say vC′∈ (N(μ+)∩End(SC)).By Claim 8,G[V(Pμ[vL(Pμ),μ2?])]and G[V(Pμare cliques.LetandTo obtain our contradiction,we distinguish the following two cases:

? Suppose that N(μ?)∩End(SC)=N(μ+)∩End(SC)={vC}.To obtain our contradiction,we distinguish the following two cases:

?Either|V(C)|=1 or|V(C)|>1 and∈E(G)is true.If y0=vR(Pμ),then by Claim 8,Q1μ in G covers V(Pμ)∪ V(C),contradicting Lemma 3.1.If y0≠vR(Pμ),then by Claim 8,Q1μLw and(y+0,Pμ)in G cover V(Pμ)∪ V(C)∪ {w},contradicting(I).

?Suppose that|V(C)|>1 and/∈E(G).Note that N(μ+)∩End(SC)={vC}.Ifthen by Lemma 3.9(1)and(3.2),N(μ+)∩X={vC}.By Lemma 2.2(ii),The setwould be an independent set of cardinality k+2,contradicting(4.2).But ifμ+vR(Pμ)∈ E(G),then Q2μ+vCμ?μLw and C(G[V(C){vC}])in G cover V(Pμ)∪V(C)∪{w},contradicting(I).

? Suppose that there exist two distinct vertices vC∈ V(C)and vC′ ∈ V(C′)such that vC∈ N(μ?)∩ End(SC)and vC′∈ N(μ+)∩ End(SC).Then,Q2and Cμ?μμ+C′in G cover V(Pμ)∪V(C)∪V(C′),satisfying(I)but not(II),a contradiction.

(2)Suppose that either N(μ?)∩ End(SC)≠ ? and N(μ+)∩ End(SC)= ?,or N(μ?)∩End(SC)= ?and N(μ+)∩End(SC)≠ ?.By symmetry,assume that N(μ?)∩End(SC)≠ ?and N(μ+)∩ End(SC)= ?.By Lemma 3.9(1)and(3.2),f((μ+,Pμ))=1.By Lemma 3.11(1),then G[V(Pμ[vL(Pμ),μ2?])]y0G[V(Pμ[μ+,vR(Pμ)]){y0}]μμ?C in G covers V(Pμ)∪ V(C),contradicting Lemma 3.1.

(3)Suppose that N(μ?)∩ End(SC)= ? and N(μ+)∩ End(SC)= ?.By Lemma 3.9(1)–(3)and(3.2),f((μ?,Pμ))=1 and f((μ+,Pμ))=1.By Lemma 3.11(1)–(2),thenμG[V(Pμin G covers V(Pμ),contradicting Lemma 3.1.

This contradiction shows that Claim 10 holds.

Claim 11 N(V(P)A1)∩Bi=?for any P∈and for any i∈{1,2}.

Proof By the symmetry,we may only prove that N(V(P)A1)∩B1=?for any P∈S′P.We distinguish the following two cases to prove Claim 11.

(1)Suppose that N(μ?)∩End(SC)=?.By Lemma 3.9(3)and(3.2),f((μ?,Pμ))=1.By Lemmas 3.15(1)–(2)and 3.16,N(V(P)A1)∩B1= ?.

(2)Suppose that N(μ?)∩ End(SC)≠ ?.By Claim 8,G[V(Pμ[vL(Pμ),μ2?])]is a clique.If P ∈,then by Lemma 3.13,N(V(P)A1)∩B1=?.If P∈,then by Lemma 3.16,N(V(P)A1)∩B1= ?.

Hence,Claim 11 is proved.

By Lemma 3.14,N(V(C))∩(V(Pμ)A2)= ?for any C ∈ SC.Combining this with Claims 2 and 7–11,ω(G?A)=k+1 and each component of G?A is a clique.

In this case,n0=n?|V(Pμ)|?|V(H)|and k0+2=k.We distinguish the following three cases to prove Fact 1.

(1)Suppose that vL(Pμ)≠ μ?and vR(Pμ)≠ μ+.By Claims 7–11,we have the following:

(2)Suppose that either vL(Pμ)= μ?and vR(Pμ)≠ μ+,or vL(Pμ)≠ μ?and vR(Pμ)= μ+.By symmetry,we assume thatμ?=vL(Pμ)and vR(Pμ)≠ μ+.By Claims 7–11,we have the following:

(3)Suppose that vL(Pμ)= μ?and vR(Pμ)= μ+.By Claims 7–11,we have the following:

Therefore,m(G)≥n?2k+1>n?2k>n?2k?1.This completes the proof of Fact 1 and also the proof of Theorem 1.4.