# Spanning Trees with At Most 6 Leaves inK1,5-Free Graphs

Authors: Pei Sun; Kai Liu
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

A graphG is called K1,5-free if G contains no K1,5 as an induced subgraph. A tree with at most m leaves is called an m-ended tree. Let σkG be the minimum degree sum of k independent vertices in G. In this paper, it is shown that every connected K1,5-free graph G contains a spanning 6-ended tree if σ7G≥G−2.


---

## Body

## 1. Introduction

We will begin with some basic definitions, notations, and terminologies used by Bondy and Murty [1]. The graph generally means a simple undirected graph G with a vertex set VG and an edge set EG. We write G for the order of G. For any v∈VG, let NGv be the set of vertices adjacent to v in G and degGv=NGv. For a nonempty subset X⊆VG, we write(1)degGX=∑x∈XdegGx,NX=x∈VG:xy∈EGfor somey∈X.For an integeri, we define NiX=x∈VG:Nx∩X=i and N≥iX=x∈VG:Nx∩X≥i. Let T be a tree. A vertex of degree one in T is called a leaf of T, and a vertex of degree at least three is called a branch vertex. If uandv are vertices of T, the path in T connecting u and v is unique and is denoted by PTu,v. Define PTu,v=PTu,v−u, PTu,v and PTu,v=PTu,v−u,v. The distance between u and v in T is denoted by dTu,v.A subsetA⊆VG is called an independent set of G if no two vertices of A are adjacent in G. The independence number of G, αG, is the order of the maximum independent set of G. For an integer k, we define(2)σkG=mindegA:Ais an independent set ofGwithA=k.For an integerr≥1, a graph G is called K1,r-free if G contains no K1,r as an induced subgraph. A tree with at most m leaves is called an m-ended tree. If T is an m-ended tree in G such that T is as large as possible, we call T the maximum m-ended tree of G. There are several well-known conditions ensuring that a graph G contains a spanning m-ended tree (see the survey paper [2]). In 1979, Win [3] obtained a sufficient condition related to an independent number for k-connected graphs, which confirms the conjecture of Las Vergnas [4].Theorem 1 (Win [3]).
LetG be a k-connected graph, and let m≥2. If αG≤k+m−1, then G has a spanning m-ended tree.There are many results on the degree sum conditions for a graph to contain a spanning tree with a bounded number of leaves or branch vertices. Among them are the following theorems.Theorem 2 (Broersma and Tuinstra [5]).
LetG be a connected graph with n vertices, and let m≥2. If σ2G≥n−m+1, then G has an m-ended tree.Theorem 3 (Gargano et al. [6]).
Letk be a nonnegative integer, and let G be a connected claw-free graph. If σk+3≥G−k−2, then G has a spanning tree with at most k branch vertices.Theorem 4 (Kano et al. [7]).
Letk be a nonnegative integer, and let G be a connected claw-free graph. If σk+3≥G−k−2, then G has a spanning tree with at most k+2 leaves.Theorem 5 (Kyaw [8]).
Every connectedK1,4-free graph with σ4G≥G−1 contains a spanning tree with at most 3 leaves.Theorem 6 (Kyaw [9]).
Let G be a connected K1,4-free graph.(1)
Ifσ3G≥G, then G has a Hamiltonian path.(2)
Ifσk+1G≥G−k/2 for an integer k≥3, then G has a spanning tree with at most k leaves.Theorem 7 (Chen et al. [10]).
LetG be a connected K1,5-free graph with n vertices. If σ5G≥n−1, then G contains a spanning 4-ended tree.In this paper, we further considerK1,5-free graphs and generalize Theorem 7 as follows.Theorem 8.
LetG be a connected K1,5-free graph. If σ7G≥G−2, then G contains a spanning 6-ended tree.Before proving Theorem 8, we first give an example to show that the condition in Theorem 8 is sharp.Letm be a positive integer, and let G be the graph obtained from a triangle xyzx and 7 copies C1,C2,…,C7 of Km by joining x to each vertex of C1∪C2, y to each vertex of C3∪C4, and z to each vertex of C5∪C6∪C7 (see Figure 1). It is easy to see that σ7G=G−3, but each spanning tree of G has at least 7 leaves. Therefore, the condition in Theorem 8 is sharp.Figure 1


## 2. Proof of Theorem 8

In this section, we will prove Theorem 8. First, we prove the following two lemmas.Lemma 1.
LetG be a connected graph with no spanning 6-ended tree, and let T be a maximum 7-ended tree of G. Then, G does not contain a 6-ended tree T′ such that VT′=VT.Proof of Lemma 1.
By way of contradiction, suppose that there is a 6-ended treeT′ in G such that VT′=VT. Since G has no spanning 6-ended tree, T′ is not a spanning tree. Hence, VG−VT′≠∅. As G is connected, there are two vertices u,v∈VG such that u∈VG−VT′ and v∈Nu∩VT′. Noting that T′+u has at most 7 leaves, we conclude that T′+u is a 7-ended tree, contrary to the maximality of T. Hence, Lemma 1 is true.Lemma 2.
LetT be a tree with n vertices. For an integer k≥3, if T has at most k leaves, then it has at most k−2 branch vertices.Proof of Lemma 2.
Assume thatT has x vertices of degree two, y branch vertices, and z leaves. Then, x+y+z=n and 2x+3y+z≤2n−1. Hence, y≤z−2≤k−2. This completes the proof of Lemma 2.
Based on the above two lemmas, we can now prove the main result of this paper.Proof of Theorem 8.
LetG be a connected K1,5-free graph. Suppose, by contradiction, that G does not contain a spanning 6-ended tree. As G is connected, there is a spanning tree T in G. By our hypothesis, i.e., G does not contain a spanning 6-ended tree, the number of leaves in T is at least 7. If the number of leaves in T is 7, then we have found a tree with exactly 7 leaves. If the number of leaves in T is more than 7, then we can delete some of the leaves, and hence, there always exists a 7-ended tree in G. We choose a maximum 7-ended tree T. By Lemma 1, T has exactly 7 leaves. Denote by U≔u1,u2,…,u7 the set of leaves of T, and let S=s1,…,sr be the set of branch vertices of T. From Lemma 2, we can conclude that 1≤r≤5. By the maximality of T, we have NU⊆VT. For i∈1,7, let Ci be the unique component of T−S containing ui, and let vi be the only neighbor of S in Ci. Denote by vi− the only neighbor of vi in S. For convenience, we let Bi≔VCi. Note that Ci=PTvi,ui. For x∈VCi−ui, let x− be the predecessor of x and x+ be the successor of x. If r≥2, let PTs1,sq be the longest path between the branch vertices. Without loss of generality, we may assume that s1,…,sq∈VPTs1,sq and sq+1,…,sr∉VPTs1,sq. For convenience, denote by si− the predecessor of si and si+ the successor of si for all i∈1,q. Set P=VPTs1,sq−s1,sq. If Bi∩NTsj≠∅ for some i∈1,7 and j∈1,r, then we call sj the branch vertex for ui.Claim 1.
For alli,j∈1,7 with i≠j, if x∈Bi∩Nuj, then x≠ui,x≠vi,x−∉NU−uj.Proof of Claim 1.
By way of contradiction, assume Claim 1 is false. Set(3)T′=T+xuj−vivi−,ifx∈ui∪vi,T+ujx+x−uk−xx−−vivi−,ifx−∈Nukfor somek≠j.
Then,T′ is a 6-ended tree with VT′=VT, which is contrary to Lemma 1. This completes the proof of Claim 1.
It follows from Claim 1 thatU is an independent set. Since G is K1,5-free, N≥5U=∅.Claim 2.
Fori∈1,7, N≥3U−Nui∩Bi=∅.Proof of Claim 2.
By way of contradiction, assume that there exists a vertexx∈N≥3U−Nui∩Bi for some i∈1,7. Then, there exist three distinct integers i1,i2,i3∈1,7−i such that ui1,ui2,ui3∈Nx. By Claim 1, we can derive that x≠ui,x≠vi and x−,x+∉NU−ui. As Gx,x−,x+,ui1,ui2,ui3≇K1,5, x−x+∈EG. Set T′=T+ui1x+ui2x+x−x+−xx+−xx−−vi2vi2−. Then, T′ is a 6-ended tree with VT′=VT, which is a contradiction. This completes the proof of Claim 2.
By an argument similar to the proof of Claim 2, we can derive thatN4U∩Bi=∅, i∈1,7.Claim 3.
N
3
U
∩
N
u
i
∩
B
i
≤
1 for all i∈1,7.Proof of Claim 3.
Suppose, on the contrary, that there are two verticesx,y∈N3U∩Nui∩Bi for some i∈1,7. Without loss of generality, assume that y∈PTx,ui. By Claim 1, x+≠y. Assume that xui1,xui2∈EG for some i1,i2∈1,7\i. Since y∈N3U, there exists j∈1,7\i,i1 such that uj∈Ny.
Ifx−x+∈EG, then T′=T+ui1x+ui2x+x−x+−x−x−xx+−vi1vi1−. Then, T′ is a 6-ended tree with a vertex set VT, which contradicts Lemma 1. Hence, x−x+∉EG. Since G is K1,5-free, it can be derived that x+ui∈EG. Set T′=T+ujy+uix++ui1x−vivi−−yy−−xx+. Then, T′ is a 6-ended tree with VT′=VT, which is contrary to Lemma 1. This completes the proof of Claim 3.Claim 4.
Ifuivi∈EG, then N≥2U∩Bi=∅ for all i∈1,7.Proof of Claim 4.
By way of contradiction, assume that Claim 4 is false. Then, there is a vertexx such that ujx∈EG for some i,j∈1,7 with j≠i. By Claim 1, x≠vi. Set T′=T+ujx+uivi−xx−−vivi−. Then, T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. This completes the proof of Claim 4.Claim 5.
For alli∈1,7, ui, Nui∩Bi, NU−ui−∩Bi, and N2U−Nui∩Bi are pairwise disjoint, where NU−ui−∩Bi=x−:x∈NU−ui∩Bi.Proof of Claim 5.
It can be easily concluded thatui∩Nui∩Bi=ui∩NU−ui−∩Bi=ui∩N2U−Nui∩Bi=Nui∩Bi∩N2U−Nui∩Bi=∅. It follows from Claim 1 that Nui∩Bi∩NU−ui−∩Bi=NU−ui−∩Bi∩N2U−Nui∩Bi=∅. This completes the proof of Claim 5.
By Claim 5, we have(4)Bi≥1+Nui∩Bi+NU−ui−∩Bi+N2U−Nui∩Bi=1+Nui∩Bi+NU−ui∩Bi+N2U−Nui∩Bi≥1+∑j=17Nuj∩Bi−N3U∩Nui∩Bi.
This together with Claim 4 implies that(5)∑j=16Nuj∩Bi≤Bi−1,ifN3U∩Bi=∅;Bi,otherwise.Claim 6.
Ifvivj∈EG for some i,j∈1,7 and i≠j, then vi−ui,vj−uj∉EG and Nuk∩Bi=Nuk∩Bj=∅ for some k∈1,7\i,j.Proof of Claim 6.
By way of contradiction, assume thatvi−ui∈EG or x∈Nuk∩Bi. Set(6)T′=T+vi−ui+vivj−vivi−−vjvj−,ifvi−ui∈EG;T+vivj+xuk−vjvj−−vivi−,ifxuk∈EG.
Then,T′ is a 6-ended tree with VT′=VT, which is contrary to Lemma 1. This completes the proof of Claim 6.
For every vertexx∈VT, define(7)fx=Nx∩U=∑i=17Nui∩x.
For every vertex setV′⊆VG, define(8)fV′=∑x∈V′fx.
Ifr≥2, we consider the following two cases.Case 1.
S
⊆
V
P
T
s
1
,
s
q.
In this case,r=q. We choose the maximum T with 7 leaves such that(C1)
T is as large as possible.(C2)
dTs1,sq is as small as possible, subject to (C1).
Without loss of generality, we may assume thatBi∩NTs1≠∅1≤i≤k1, Bi∩NTs2≠∅k1+1≤i≤k2,…,Bi∩NTsq≠∅kq−1+1≤i≤kq, and degTs1≥degTsq. Hence, kq=7 and degTsq≤4. Set(9)P=VPTs1,sq.
LetT1=T1,…,T9 be the family of graphs shown in Figure 2. Then, in Case 1, T∈T1.
The following claim plays a crucial role in the proof of Case 1.Figure 2
T
1
=
T
1
,
…
,
T
9.Claim 7.
Letxandx+ be two consecutive vertices in PTs1,sq such that xui1,x+ui2∈EG, where i1,i2∈1,7 and i1≠i2. Let sjt be the branch vertex for uit, where t∈1,2. If G has no 6-ended tree, then sj1∈VPTs1,x and sj2∈VPTx+,sq.Proof of Claim 7.
By way of contradiction, assume thatsj1∉VPTs1,x. Set T′=T+xui1+x+ui2−xx+−vi2vi2−. Then, T′ is a 6-ended tree with VT′=VT, which is contrary to Lemma 1. Similarly, sj2∉VPTx+,sq. This completes the proof of Claim 7.Claim 8.
Letsj be the branch vertex for ui for some i∈1,7 and j∈2,q−1. Then, sj−,sj+∉Nui. Specifically, s1+∉Nui for all i∈1,k1 and sq−∉Nui for all i∈kq−1+1,7.Proof of Claim 8.
Suppose, for contradiction, thatsj−∈Nui for some i∈kj−1+1,kj. Set T′=T+sj−ui−sj−sj. Hence, T′ is a 6-ended tree with VT′=VT, contradicting Lemma 1. Hence, sj−∉Nui. Likewise, sj+∉Nui. This completes the proof of Claim 8.Claim 9.
IfdegTsi=3 for some i∈1,q, then si∉N4U.Proof of Claim 9.
By way of contradiction, supposedegTs1=3 and s1∈N4U. Hence, there exist two integers i,j∈1,7\1,k1 with i≠j such that ui,uj∈Ns1. By Claim 8, we can see that s1+ is not the branch vertex for ui or uj. This together with s1∈N4U, by applying Claim 7, implies that s1+ui,s1+uj∉EG. This and Claim 8 imply that Gs1,s1+,Ns1∩U≅K1,5, which is a contradiction. Hence, s1∉N4U, and similarly, if degTsq=3, then sq∉N4U.
The proof of Case 1 has been divided into 6 subcases.Subcase 1.
T
≅
T
1.
Without loss of generality, we may assume thatBi∩NTs1≠∅1≤i≤2, Bi∩NTs2≠∅3≤i≤5,andBi∩NTs3≠∅6≤i≤7.
We chooseT such that(C3)
∑i=35Bi is as large as possible, subject to (C1) and (C2).Subclaim 1.
For every vertexx∈P\s2,fx≤2.Proof of Subclaim 1.
By way of contradiction, suppose that there is a vertexx∈P\s2 such that fx=3. Then, there exist three distinct integers i1,i2,i3∈1,7 such that ui1,ui2,ui3∈Nx. By (C2), we can see that i1,i2,i3∩3,5≠∅. If x−x+∈EG, set T′=T+x−x++xui1+xui2−xx−−xx+−vi1vi1−. Hence, T′ is a 6-ended tree with VT′=VT, which is contrary to Lemma 1. Thus, x−x+∉EG. Since G is K1,5-free, there exists j1∈i1,i2,i3 such that x−uj1∈EG or x+uj1∈EG, contradicting Claim 7. This completes the proof of Subclaim 1.
SetP′=P\s2. If for every vertex x∈P′,fx≤1, then ∑i=17Nui∩P′≤P′. Otherwise, suppose that there are s vertices x1,…,xs in PTs1,s2 satisfying fxj=2 for all j∈1,s. Define Pi=PTxi,xi+1, P0=PTs1+,x1, and Ps=PTxs,s2. Therefore, PTs1,s2=∪i=0sPi.
For everyi∈1,s−1, fxi=2. It follows from Claim 7 and (C2) that fxi+=0. Hence, ∑j=17Nuj∩Pi≤Pi. Since fs2−=0, ∑j=17Nui∩Ps≤Ps. Thus, ∑j=17Nuj∩PTs1,s2≤PTs1,s2. Therefore,(10)∑j=17Nui∩P′≤P′.Subclaim 2.
∑
i
=
3
5
∑
j
=
1
7
N
u
j
∩
B
i
+
∑
i
=
1
7
N
u
i
∩
s
2
≤
∑
i
=
3
5
B
i
.Proof of Subclaim 2.
Ifs2ui∈EG, by (C2), i∈3,5, say i=3. Then, N3U∩Nu3∩B3=∅. Otherwise, assume that x∈N3U∩Nu3∩B3 and xuj∈EG for some j∈1,7\i. Then by (C2), j∈3,5, that is, xu4,xu5∈EG. If u3=v3, the result holds. Hence, we assume that u3≠v3. Since Gs2,v3,v4,v5,u3,s2+≇K1,5, by Claims 4 and 6, v4v5,s2+v3,s2+vt∩EG≠∅ for some t∈4,5. Set(11)T′=T+xu4+v4v5−v4s2−v5s2,ifv4v5∈EG;T+s2u3+s2+v3−s2s2+−v3s2,ifs2+v3∈EG;T+xut+s2+vt−s2s2+−vts2,ifs2+vt∈EGfor somet∈4,5.
Then,T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. It follows from (5) that(12)∑i=35∑j=17Nuj∩Bi+∑i=17Nui∩s2≤∑i=35Bi.Subclaim 3.
∑
i
=
1
2
∑
j
=
1
7
N
u
j
∩
B
i
+
f
s
1
+
∑
i
=
1
7
N
u
i
∩
P
T
s
1
,
s
2
≤
∑
i
=
1
2
B
i
+
P
T
s
1
,
s
2.Proof of Subclaim 3.
If there are three distinct integersi1,i2,i3 in 1,7 such that s1ui1,s1ui2,s1ui3∈EG, then since G is K1,5-free, then s1+v1∈EG, which contradicts (C2).
Ifs1ui1,s1ui2∈EG for vi1−≠s1,vi2−≠s1, by (C2), i1,i2∈3,5. Without loss of generality, set i1=3,i2=4. Since Gs1,v1,v2,ui1,ui2,s1+≇K1,5, by (C2) and Claims 1 and 6, we have v1v2∈EG. Also by Claim 6, s1u1,s1u2∉EG. Moreover, N3U∩Bi∩Nui=∅ for all i∈1,2.
Ifs1ui∈EG for some i∈3,7, set i=3. Then by Claim 7, fs1+≤1. If there is a vertex x∈VPTs1+,x1 such that fx=0, then ∑i=17Nui∩PTs1,s2≤PTs1,s2−1. Otherwise, for every x∈VPTs1+,x1, fx=1. By Claim 7, xu3∈EG. Specifically, x1−u3∈EG. By applying Claim 7, we get a contradiction. Hence, ∑i=17Nui∩PTs1,s2≤PTs1,s2−1. If s1uj∈EG for some j∈1,2, then N3U∩Nuj∩Bj=∅. Suppose, for contradiction, x∈N3U∩Nuj∩Bj and xui1∈EG. Then by (C3), i1∈6,7. Set T′=T+s1uj+xui1−xx−−vi1vi1−, which contradicts (C2). This together with (5) implies that the result holds.
It follows from Subclaims 2-3 that(13)degU=∑i=17Nui∩PTs1,sq+∑i=17∑j=17Nuj∩Bi≤∑i=17Nui∩P′+∑i=17Bi≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 1.Claim 10.
IfT∈T1\T1 and there is a vertex x∈P, then fx≤2.Proof of Claim 10.
Assume that there is a vertexx∈P such that fx=3. Then, there exist three distinct integers i1,i2,i3∈1,7 such that ui1,ui2,ui3∈Nx. Set T′=T+xui1+xui2+xui3−vi1vi1−−vi2vi2−−vi3vi3−. Then, T′ is a maximum tree with 7 leaves. Since s1,sq are branch vertices, by (C2), degT′s1≥3 and degT′sq≥3. This implies that we can find a tree T′ such that T′≅T1. This completes the proof of Claim 10.
Thus, in the following subcases, we suppose that, for every vertexx∈P, fx≤2.
If for every vertexx∈P,fx≤1, then ∑i=17Nui∩P≤P. Otherwise, suppose that there are s vertices x1,x2,…,xs in P satisfying fxj=2 for all j∈1,s. Define Pi=PTxi,xi+1, P0=PTs1+,x1, and Ps=PTxs,sq. Therefore, P=∪i=0sPi.
It follows from Claim 7, Claim 8, and (C2) thatxi+≠xi+1. Since fxi=2, by applying Claim 7 with x,x+=xi,a1 and (C2), we can derive that either fa1=0 or there exists some k∈1,7 such that ajuk∈EG for all j∈1,t. In the latter case, combining with fxi+1=2, we can conclude that atandxi+1 contradict Claim 7. Thus, fa1=0, and hence, ∑j=17Nuj∩Pi≤Pi, where i∈0,s−1.
Ifxs≠sq−, similar arguments apply to Ps and then ∑j=17Nuj∩Ps≤Ps. Thus,(14)∑i=17Nui∩P≤P.
Ifxs=sq−, by Claim 7, we can deduce that squi∉EG for all vi−≠sq. Hence,(15)∑i=17Nui∩P≤P+1.
In the following, ifT∈T1\T1,T5, we choose T such that(C4)
∑i=1k1Bi is as large as possible, subject to (C1) and (C2).Subcase 2.
T
≅
T
2.
Without loss of generality, we may assume thatdegTs1=6 and degTs2=3. If s1ui∈EG, by (C2), i∈1,5.
SinceGs1,Ns1≇K1,5, there are three integers in 1,5, say 1,2,and3, such that v1v2,v2v3∈EG or v1v2,s1+vi∈EG for some i∈1,3. Hence, s1u1,s1u2∉EG and N3U∩Bi∩Nui=∅ for all i∈1,2.(i)v2v3∈EG. In this case, s1u3∉EG and N3U∩Bi∩Nui=∅ for all i∈1,3. If s1u4∈EG, by Claim 6 and (C2), we can derive that N3U∩B4∩Nu4=∅. Hence, ∑i=15∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=15Bi−3.(ii)s1+v3∈EG. Then, s1u3∉EG, since otherwise T′=T+s1u3+s1+v3−s1s1+−v3s1 is a 6-ended tree with VT′=VT, which contradicts Lemma 1. If s1u4∈EG, then assume that x∈N3U∩B4∩Nu4 and xuj∈EG for some j∈1,7\4,5. By (C2), j∈1,3. Set(16)T′=T+v1v2+xuj−v1s1−v2s1,ifj∈1,2;T+s1+v3+xuj−v3s1−s1s1+,ifj=3.Then,T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. Thus, N3U∩B4∩Nu4=∅. Hence, ∑i=15∑j=17Nuj∩Bi+∑i=15Nui∩s1≤∑i=15Bi−3.(iii)
s1+v2∈EG. Then by similar arguments, s1+v1∈EG. If s1u3∈EG, then we claim that N3U∩Nu3∩B3=∅. If u3=v3, then the above claim is true. Hence, u3≠v3. Assume x∈N3U∩Nu3∩B3 and xuj∈EG. By similar arguments, we have j∉1,2∪6,7. Thus, xu4,xu5∈EG. Since Gs1,u3,v3,v4,v5,v2≇K1,5, by Claims 1, 4, and 6, v3vt,v4v5,v2vt∩EG≠∅, where t∈4,5. Set(17)T′=T+v3vt+xut−v3s1−vts1,ifv3vt∈EG;T+v4v5+xu4−v4s1−v5s1,ifv4v5∈EG;T+xut+v2vt−vts1−v2s1,ifv2vt∈EG.
Then,T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. Hence, ∑i=15∑j=17Nuj∩Bi+∑i=15Nui∩s1≤∑i=15Bi−2. Above all, we have(18)∑i=15∑j=17Nuj∩Bi+∑i=15Nui∩s1≤∑i=15Bi−2.
If there are three distinct integersi1,i2,i3∈1,5 such that s2ui1,s2ui2,s2ui3∈EG, then s2−≠s1. Since Gs2,ui1,ui2,ui3,v3,s2≇K1,5, we have s2−uij∈EG for some j∈1,3, which contradicts Claim 7.
From (C4),N3U∩Nui∩Bi=∅ for all i∈6,7. If fs2≤2, then ∑i=67∑j=17Nuj∩Bi+∑i=17Nui∩s2≤∑i=67Bi.
Iffs2≥3, there is an integer j∈1,5 such that s2uj∈EG. By symmetry, set j=5. Then, s1s2∉EG and s1+∉NU. Otherwise, if s1s2∈EG, set T′=T+s2u5−s1s2. If s1+ui∈EG, then i∈6,7. Set T′=T+s2u5+s1+ui−s1s1+−vis2. Then, T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. Moreover, fs2−≤1. This together with the proof of (14) implies that ∑i=67∑j=17Nuj∩Bi+∑i=17Nui∩s2+∑i=17Nui∩P≤∑i=67Bi+P.
In either case, we can get(19)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s2+∑i=17Nui∩P≤∑i=67Bi+P−1≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 2.Subcase 3.
T
≅
T
3.
In this case,T satisfies degTs1=5 and degTs2=4. Without loss of generality, we may assume that Bi∩NTs1≠∅1≤i≤4 and Bi∩NTs2≠∅5≤i≤7.
Ifs1ui∈EG, then i∈1,5. Otherwise, we can find a tree satisfying Subcase 2. Analysis similar to that of Subcase 2 shows that(20)∑i=14∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=14Bi−1.
Ifs2ui∈EG for some i∈5,7, then set i=5. Then, N3U∩Nu5∩B5=∅. If u5=v5, the result is true. Hence, u5≠v5. Suppose, for contradiction, xuj∈EG for some j∈1,7\5. By (C4), we have xu6,xu7∈EG. Since G is K1,5-free, v6v7,s2−vt∩EG≠∅ for some t∈6,7. Set(21)T′=T+v6v7+xu6−v6s2−v7s2,ifv6v7∈EG;T+s2−vt+xut−vts2−s2−s2,ifs2−vt∈EGfor somet∈6,7.
Then,T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. Hence, if s2ui∈EG for some i∈5,7, then N3U∩Nui∩Bi=∅.
Ifs2ui∈EG for some i∈1,4, then set i=4. Then, fs2−≤1 and s1+∉NU, that is, ∑i=17Nui∩P≤P−1.
Ifs2ui1,s2ui2∈EG for some i1,i2∈1,4, then set i1=3andi2=4. Since Gs2,v5,v6,v7,ui1,ui2≇K1,5, vivj∈EG for some 5≤i≠j≤7, say i=5andj=6. Hence, s2u5,s2u6∉EG. By similar arguments, we can derive that if s2u7∈EG, then N3U∩Nu7∩B7=∅. Hence,(22)∑i=57∑j=17Nuj∩Bi+∑i=17Nui∩s2≤∑i=57Bi.
Above all, we have(23)∑i=57∑j=17Nuj∩Bi+∑i=17Nui∩s2+∑i=17Nui∩P≤∑i=57Bi+P.
This together with (20) shows that(24)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s2+∑i=17Nui∩P≤∑i=17Bi+P−1≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 3.Subcase 4.
T
≅
T
4.
In this case,T satisfies degTs1=5 and degTs2=degTs3=3. Without loss of generality, we may assume that Bi∩NTs1≠∅1≤i≤4, Bi∩NTs2≠∅i=5,andBi∩NTs3≠∅6≤i≤7.Subclaim 4.
s
1
u
j
∉
E
G for all j∈5,7. Similarly, s2ui∉EG for all i∈6,7 and s3ui∉EG for all i∈1,5.Proof of Subclaim 4.
By way of contradiction, suppose thats1uj∈EG for some j∈5,7. Set T′=T+s1uj−vjvj−. Then, T′≅T2, which is a contradiction to Subcase 2. Similarly, suppose that s2u6∈EG or s3uj∈EG for some j∈1,5. Set T′=T+s2u6−v6s3 or T′=T+s3uj−vjvj−. Then, T′≅T3, which is a contradiction to Subcase 3. This completes the proof of Subclaim 4.Subclaim 5.
∑
i
=
1
7
N
u
i
∩
B
5
+
f
s
2
+
∑
i
=
1
7
N
u
i
∩
P
T
s
1
,
s
2
≤
B
5
+
P
T
s
1
,
s
2.Proof of Subclaim 5.
It follows from (C4) that(25)∪i=14Nui∩B4=∅.
Its2u5∈EG, then N2U∩B5=∅. By way of contradiction, assume that x∈N2U∩B5 and xuj∈EG. By (25), j∈6,7. Set T′=T+s2u5+xuj−xx−−vjvj−. Then, dT′s1,s2<dTs1,s3, which contradicts (C2).
Ifs2ui∈EG for vi−≠s2, then i∈1,4. Hence, VPTs1,s2≠∅. By Claim 7, fs2−≤1. Moreover, s1+∉NU. Otherwise, assume that s1+uj∈EG. Then, j∈5,7. Set T′=T+s1+uj+s2ui−s1s1+−vjvj−. T′ is a 6-ended tree with VT′=VT, which is contrary to Lemma 1. Hence, s1+∉NU. By a similar argument as in the proof of (10), we have(26)∑i=17Nui∩VPTs1,s2≤PTs1,s2−1.
Thus,∑i=17Nui∩​B5+fs2+∑i=17Nui∩P\s2≤B5+P\s2. This completes the proof of Subclaim 5.Subclaim 6.
f
s
3
+
∑
i
=
1
7
N
u
i
∩
P
T
s
2
,
s
3
≤
P
T
s
2
,
s
3.Proof of Subclaim 6.
From (C4), we have(27)∩i=14Nui∩Bj=∅,for allj∈6,7.
Ifs3ui∈EG such that vi−=s3, then we assert that N3U∩Bi=∅. By way of contradiction, assume that x∈N3U∩Bi and xuj∈EG for some j∈1,5. By (34), j=4. Set T′=T+s3ui+xuj−xx−−vjvj−. Then, T′≅T3, which is a contradiction to Subcase 3. Hence, our assertion holds.
Ifs3ui∈EG such that vi−≠s3, then s2s3∉EG and hence fs2+=0,fs3−≤1. Otherwise, assume that s2+ui1∈EG or s3−ui2∈EG. Then, i1∈1,4 and i2≠i. Set(28)T′=T+s2+ui1−s2s2+,ifs2+ui1∈EG;T+s3−ui2+s3ui−s3−s3−vi2vi2−,ifs3−ui2∈EG.
Then,T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. By the proof of (14), we have ∑i=17Nui∩PTs2,s3≤PTs2,s3−1.
Above all, we can get thatfs3+∑i=17Nui∩PTs2,s3≤PTs2,s3. This completes the proof of Subclaim 6.
Similar consideration as Subcase 2 shows that(29)∑i=14∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=14Bi−1.
Combining with Subclaims 5 and 6, (5), and (29), we have(30)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s3+∑i=17Nui∩P≤∑i=17Bi+P−1≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 4.Subcase 5.
T
≅
T
5.
In this case,T satisfies degTs1=degTs2=4 and degTs3=3. Without loss of generality, we may assume that Bi∩NTs1≠∅1≤i≤3, Bi∩NTs2≠∅4≤i≤5,andBi∩NTs3≠∅6≤i≤7. We choose T such that(C5)
∑i=67Bi is as small as possible, subject to (C1) and (C2).
It is easy to check thats1ui∉EG for all i∈4,7. If s1ui∈EG for some i∈1,3, then set i=1. We assert that N3U∩Nu1∩B1=∅. By way of contradiction, assume that x∈N3U∩Nu1∩B1 and hence xu2,xu3∈EG, since otherwise we can find a tree satisfying Subcase 4. If u1=v1, the assertion holds. Hence, we assume that u1≠v1. Since Gs1,u1,v1,v2,v3,s1+≇K1,5, by Claims 1, 4, and 6, we have v2v3,s1+vt∩EG≠∅ for some t∈2,3. Set(31)T′=T+xu2+v2v3−v2s1−v3s1,ifv2v3∈EG;T+xut+s1+vt−vts1−s1s1+,ifs1+vt∈EG.
Then,T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. Hence,(32)∑i=13∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=13Bi.
Ifs2ui∈EG, by (C2), i∈4,5. Moreover, we have N3U∩Nui∩Bi=∅. By way of contradiction, assume that x∈N3U∩Nui∩Bi and xuj∈EG for some j∈1,7\4,5. Set T′=T+s2ui+xuj−xx−−vjvj−. Then, T′≅T1 or T′≅T3, which is a contradiction. Hence, by (5),(33)∑i=45∑j=17Nuj∩Bi+∑i=17Nui∩s2≤∑i=45Bi.
From (C5),N3U∩Nui∩Bi=∅ for all i∈6,7. Thus, if fs3≤2, then(34)∑i=17Nui∩P\s2+fs3+∑i=67∑j=17Nuj∩Bi≤∑i=67Bi+P\s2.
Iffs3=3, then assume that s3ui∈EG for some i∈1,5. Then, s2+≠s3, fs3−≤1, and s2+∉NU. Hence, by (14),(35)∑i=17Nui∩P\s2≤P\s2−1.
In either case, (34) holds. Therefore,(36)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s2,s3+∑i=17Nui∩P\s2≤∑i=17Bi+P\s2≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 5.Subcase 6.
T
∈
T
6
,
…
,
T
9.
IfdegTs1=4, then similar arguments as in the proof of Subcase 4 show that(37)∑i=13∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=13Bi.
IfdegTs1=3 and s1ui∈EG for some vi−=s1, then N3U∩Nui∩Bi=∅. Otherwise, we can find a tree satisfying degTs1=4.
IfdegTs1=3 and s1ui∈EG for some vi−≠s1, then we can find a tree satisfying degTs1=4. Hence, we can assume that s1ui∉EG for all vi−≠s1.
IfT≅T6, then s1ui∉EG for i∈4,7 and s2ui∉EG for i≠4. If s2u4∈EG, by similar arguments, we have N3U∩B4∩Nu4=∅. Hence, ∑j=17Nuj∩B4+∑i=17Nui∩s2≤B4. If s2−≠s1, then fs2−≤1. Otherwise, we assume that s2−ui1,s2−ui2∈EG. If i1,i2∩5,7≠∅, then set T′=T+s2−ui−s2−s2, where i∈i1,i2∩5,7. Then, T′ is a 6-ended tree with VT′=VT, which contradicts Lemma 1. Thus, i1,i2∈1,3. Set T′=T+s2−ui1+s2−ui2−vi1s1−vi2s1, which is contrary to (C2). Therefore, by (14), we can derive that(38)∑i=17Nui∩PTs1,s2≤PTs1,s2.
Applying similar arguments toPTs2,s3 in the reverse order, we have(39)∑i=17Nui∩PTs2,s3≤PTs2,s3.
Hence,(40)∑i=17Nui∩P\S≤P\S.
Therefore,(41)∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s2,s3+∑i=17Nui∩P\s2≤∑i=17Bi+P\s2≤G−3.
IfT≅T7, then s1ui∉EG for i∈4,7 and s4ui∉EG for i∈1,5. If s2u4∈EG, by (C2) and (C4), N3U∩Nu4∩B4=∅. If s2ui∈EG for some vi−≠s2, by (C2), i∈1,3. Hence, s1+≠s2, fs1+=0, and fs2−≤1. Thus,(42)∑i=17Nui∩B4+∑i=17Nui∪s2+∑i=17Nui∩PTs1,s2≤B4+PTs1,s2.
Similarly, ifs3ui∈EG for some vi−≠s3, then i∈1,4,s2s3∉EG, fs2+=0, and fs3−≤1. Hence,(43)∑i=17Nui∩B5+∑i=17Nui∩s3+∑i=17Nui∩PTs2,s3≤B5+PTs2,s3.
Ifs4ui∈EG for some i∈6,7, then it follows from (C4) that N3U∩Nui∩Bi=∅. Then,(44)∑i=67∑j=17Nuj∩Bi∪s4≤∑i=67Bi.
Ifs3+≠s4, then by similar arguments, fs3+=0. Thus, ∑i=17Nui∩PTs3,s4≤PTs3,s4. Therefore,(45)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s4+∑i=17Nui∩P≤∑i=17Bi+P\s2,s3≤G−3,which implies that σ7G≤G−3, which is a contradiction.
IfT≅T8, then siuj∉EG for some i∈1,2,4 and vj−≠si. By similar arguments, we have(46)∑i=12∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=12Bi.
Similarly,(47)∑i=34∑j=17Nuj∩Bi+∑i=17Nui∩s2≤∑i=34Bi,(48)∑i=67∑j=17Nuj∩Bi+∑i=17Nui∩s4≤∑i=67Bi,(49)∑i=17Nui∩B5+∑i=17Nui∩PTs2,s3+fs3≤B5+PTs2,s3.
Ifs2−≠s1, then fs2−=0. Hence, by (14), ∑i=17Nui∩PTs1,s2≤PTs1,s2. Similarly, ∑i=17Nui∩PTs3,s4≤PTs3,s4. This together with (46)–(49) implies that(50)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s4+∑i=17Nui∩P≤∑i=17Bi+P\s2≤G−3,which implies that σ7G≤G−3, which is a contradiction.
IfT≅T9, we have(51)∑i=12∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=12Bi,(52)∑i=67∑j=17Nuj∩Bi+∑i=17Nui∩s5≤∑i=67Bi.
Fori∈2,4, if siuj∈EG, then vj−=si. Thus,(53)∑j=17Nuj∩Bi+∑j=17Nuj∩si≤Bi.
By similar arguments, (40) holds. Therefore,(54)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s4+∑i=17Nui∩P≤∑i=17Bi+P\s2,s3,s4≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 6. Since Subcases 1–6 are proved, Case 1 is proved.Case 2.
S
⊈
V
P
T
s
1
,
s
q
.
LetT2=T10,T11,T12 be the family of graphs shown in Figure 3. Hence, T∈T2. Without loss of generality, we may assume that Bi∩NTs1≠∅1≤i≤k1 and Bi∩NTsq≠∅6≤i≤7.
We choose the maximal treeT with 7 leaves such that(C6)
dTs1,sq+dTs2,sr is as small as possible, subject to (C1) and (C2).(C7)
∑i=1k1Bi is as large as possible, subject to (C1), (C2), and (C6).Figure 3
T
2
=
T
10
,
T
11
,
T
12.Claim 11.
For every vertexx∈VPTs2,sr∪VPTs1,sq, Nx∩U≤1.Proof of Claim 11.
By way of contradiction, assume thatxui,xuj∈EG for some i,j∈1,7 and i≠j. Set T′=T+xui+xuj−vivi−−vjvj−. Then, T′∈T1 or dT′s1,sq+dT′s2,sr<dTs1,sq+dTs2,sr. In either case, we get a contradiction. This completes the proof of Claim 11.
From Claim 11, we have(55)∑i=17Nui∩PTs1,sq≤PTs1,sq,(56)∑i=17Nui∩PTs2,sr≤PTs2,sr.
The proof of Case 2 has been divided into two subcases.Subcase 7.
T
≅
T
10.
In this case,T satisfies(i)
degTs1=4,degTs2=degTs3=degTs4=3.(ii)
s2∈VPTs1,s3, s4∉VPTs1,s3, subject to (i).
Without loss of generality, we may assume thatBi∩NTs1≠∅1≤i≤3,Bi∩NTs2=∅1≤i≤7,Bi∩NTs3≠∅6≤i≤7,andBi∩NTs4≠∅4≤i≤5 (see Figure 3).Subclaim 7.
N
s
4
∩
U
−
u
4
,
u
5
=
∅.Proof of Subclaim 7.
Suppose, contrary to our claim, thats4uj∈EG for some j∈1,7\4,5. Set(57)T′=T+s4uj−s2s2′+,j∈1,3,T+s4uj−vjvj−,j∈6,7,where s2′+ is the successor of s2 on PTs2,s4. Then, T′∈T1, which is a contradiction to Case 1. This completes the proof of Subclaim 7.Subclaim 8.
s
1
u
j
∉
E
G for all j∈1,7\1,3.Proof of Subclaim 8.
By way of contradiction, assume thats1ui∈EG for some i∈1,7\1,3. Set T′=T+s1ui−vivi−. Then, T∈T1, which is a contradiction.
Ifs3ui∈EG for some i∈6,7, then N3U∩Nui∩Bi=∅. If s3ui∈EG for i∉6,7, then i∈1,3, since otherwise we can find a tree satisfying Case 1, which is a contradiction. Then, s2+≠s3 and s2+∉NU. Otherwise, set T′=T+s2+ui−s2s2+. Then, T′ contradicts Lemma 1 or (C6). Hence, by (5) and (14), we have(58)∑i=67∑j=17Nui∩Bi+∑i=17Nui∩PTs1,s3+∑i=17Nui∩s3≤∑i=67Bi+PTs1,s3.
This together with Subcase 4 and (55)–(58) implies that(59)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩s1,s3,s4+∑i=17Nui∩P∪PTs2,s4≤∑i=17Bi+PTs2,s4+PTs1,s3≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 7.Subcase 8.
EitherT≅T11 or T≅T12.Subclaim 9.
N
s
1
∩
U
−
u
1
,
u
2
=
∅ and Nsq∩U−u6,u7=∅.Proof of Subclaim 9.
On the contrary, suppose thats1ui∈EG for some i∈3,7. Set T′=T+s1ui−vivi−. Hence, T′∈T1 or T′≅T10. In either case, we get a contradiction. Similarly, Nsq∩U−u6,u7=∅. This completes the proof of Subclaim 9.
By Subclaim 9, we can see that(60)∑i=12∑j=17Nuj∩Bi+∑i=17Nui∩s1≤∑i=12Bi.
Similarly,(61)∑i=67∑j=17Nuj∩Bi+∑i=17Nui∩sq≤∑i=67Bi,(62)∑j=17Nuj∩B5+∑i=17Nui∩sq−1≤B5.
Combining with (55)–(62), we have(63)degU=∑i=17∑j=17Nuj∩Bi+∑i=17Nui∩PTs1,sq∪PTs2,sr≤∑i=17Bi+PTs2,sr+PTs1,sq≤G−3,which implies that σ7G≤G−3, which is a contradiction. This completes the proof of Subcase 8. Since Subcases 7-8 are proved, Case 2 is proved.
Ifr=1, since Gs1,v1,v2,v3,v4,v5,v6,v7≇K1,5, there exist two integers i,j∈1,7 such that vivj∈EG. Hence, ui≠vi and uj≠vj. Set T′=T+vivj−vivi−. Then, T′ has exactly two branch vertices, which is a contradiction to Case 1. This completes the proof of Theorem 8.



---

*Source: 1348348-2019-10-03.xml*