ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 49-61
On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices*
*
Long-Tu Yuan, Xiao-Dong Zhang
Department of Mathematics, and Ministry of Education, Key Laboratory of Scientific and Engineering Computing, Shanghai Jiao Tong University, 800 Dongchuan Road, Shanghai, 200240, P. R. China
Received 1 August 2015, accepted 19 November 2015, published online 21 October 2016
The Erdos-Sos Conjecture states that if G is a simple graph of order n with average degree more than k — 2, then G contains every tree of order k. In this paper, we prove that Erdos-Sos Conjecture is true for n = k + 4.
Keywords: Erdôs-S6s Conjecture, tree, maximum degree. Math. Subj. Class.: 05C05, 05C35
1 Introduction
The graphs considered in this paper are finite, undirected, and simple (no loops or multiple edges). Let G = (V(G), E(G)) be a graph of order n, where V(G) is the vertex set and E (G) is the edge set with size e(G). The degree of v e V (G), the number of edges incident to v, is denoted dG(v) and the set of neighbors of v is denoted N(v). If u and v in V(G) are adjacent, we say that u hits v or v hits u. If u and v are not adjacent, we say that u misses v or v misses u. If S C V(G), the induced subgraph of G by S is denoted by G[S]. Denote by D(G) the diameter of G. In addition, ¿(G), A(G) and avedeg(G) = j/jf)| are denoted by the minimum, maximum and average degree in V(G), respectively. Let T be a tree on k vertices. If there exists an injection g : V(T) ^ V(G) such that g(u)g(v) e E(G) if uv e E(T) for u, v e V(T), we call g an embedding of T into G and G contains a copy of T as a subgraph, denoted by T C G. In addition, assume that T' C T is a subtree of T
*This work is supported by National Natural Science Foundation of China (Nos.11271256 and 11531001), The Joint Israel-China Program (No.11561141001), Innovation Program of Shanghai Municipal Education Commission (No.14ZZ016) and Specialized Research Fund for the Doctoral Program of Higher Education (No.20130073110075).
E-mail addresses: yuanlongtu@sjtu.edu.cn (Long-Tu Yuan), xiaodong@sjtu.edu.cn (Xiao-Dong Zhang) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
49
Ars Math. Contemp. 13 (2017) 107-123
and g' is an embedding of T' into G. If there exists an embedding g : V(T) ^ V(G) such that g(v) = g'(v) for all v e V(T'), we say that g' is T-extensible. In 1959, ErdOs and Gallai [6] proved the following theorem.
Theorem 1.1. Let G be a graph with avedeg(G) > k — 2. Then G contains a path of order k.
Based on the above result, Later Erdos and Sos proposed the following well known conjecture (for example, see [5]).
Conjecture 1.2. Let G be a graph with avedeg(G) > k — 2. Then G contains every tree on k vertices as a subgraph.
Various specific cases of Conjecture 1.2 have already been proven. For example, Brandt and Dobson [2] proved the conjecture for graphs having girth at least 5. Balasubramanian and Dobson [1] proved this conjecture for graphs without any copy of K2,s, s < -k +1. Li, Liu and Wang [15] proved the conjecture for graphs whose complement has girth at least 5. Dobson [3] improved this to graphs whose complements do not contain K2,4. More results on this conjecture can be referred to [7, 8, 9] and [11, 12]. On the other hand, in 2003, Mclennan [10] proved the following theorem.
Theorem 1.3. Let G be a graph with avedeg(G) > k — 2. Then G contains every tree of order k whose diameter does not excess 4 as a subgraph.
In 2010, Eaton and Tiner [4] proved the the following two theorems.
Theorem 1.4. [4] Let G be a graph with avedeg(G) > k — 2. If 5(G) > k — 4, then G contains every tree of order k as a subgraph.
Theorem 1.5. [4] Let G be a graph with avedeg(G) > k — 2. If k < 8, then G contains every tree of order k as a subgraph.
In 1984, Zhou [17] proved that Conjecture 1.2 holds for k = n. Later, Slater, Teo and Yap [13] and Wozniak [16] proved that Conjecture 1.2 holds for k = n — 1 and k = n — 2, respectively.
Theorem 1.6. [16] Let G be a graph of order n with avedeg(G) > k — 2. If k = n — 2, then G contains every tree of order k as a subgraph.
Recently, Tiner [14] proved that Conjecture 1.2 holds for k = n — 3.
Theorem 1.7. [14] Let G be a graph of order n with avedeg(G) > k — 2. If k > n — 3, then G contains every tree of order k as a subgraph.
In this paper, we establish the following:
Theorem 1.8. Let G be a graph of order n with avedeg(G) > k — 2. If k > n — 4, then G contains every tree of order k as a subgraph.
L.-T. Yuan andX.-D. Zhang: On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices 51
2 Proof of Theorem 1.8
Let T be any tree of order k. If k > n — 3, or k < 8 or the diameter of T is at most 4, the assertion holds by Theorems 1.3, 1.5 and 1.7. We only consider k = n — 4 > 9, D(T) > 5 and prove the assertion by the induction. Clearly the assertion holds for n = 6. Hence assume Theorem 1.8 holds for all of the graphs of order fewer than n and let G be a graph of order n. If there exists a vertex v with dG(v) < |_f J, then avedeg(G — v) > k — 2 and the assertion holds by Theorems 1.7. Furthermore, by Theorem 1.4, without loss of generality, there exists a vertex z in V (G) such that |_ f J < dG (z ) = ¿(G) < k —5. Without loss of generality, we can assume that e(G) = 1 + |_ 2 (k — 2)(k + 4) J. Let T be any tree of order k with a longest path P = a0ai... ar_iar and NT(ai) \ {a2} = {&i,..., bs} and Nt(ar-1) \ {ar-2} = {c1,..., ct}. Since avedeg(G) > k — 2, we can consider the following cases: A(G) = k + 3, k + 2, k + 1, k, k — 1.
2.1	A(G) = k + 3
Let u € V(G) be such vertex that dG(u) = k + 3 and let G' = G — {u, z} and T' = T — {a1, b1,..., bs}. Then e(G') > e(G) — (k + 3) — (k — 5) + 1 > 2(k + 4)(k — 2) — (k + 3) — (k — 5) +1 = 1 (k2 — 2k — 2). So avedeg(G') > (k2 — 2k — 2)/(k + 2) > k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. Let f' be an embedding of T' into G'. Then let f = f' in T' and f (a1) = u, X = V(G) \ f'(V(T')). Since dG(u) = k + 3, u hits at least s vertices in X. Hence f can be extended to an embedding of T into G or we can say that f is T—extensible.
Remark: For the remainder of this paper we shall always let f' be an embedding of T' into G' and when we do not define the value of f on any vertex of T', we always let f = f' on those vertices.
2.2	A (G) = k + 2
Let u € V(G) be such vertex that dG (u) = k + 2. Then there exists only one vertex x € V(G) \ {u} not adjacent to u. We consider two subcases: dG(x) < k — 2 and
dG(x) > k — 1.
2.2.1	dG(x) < k - 2
Let G' = G — {u, x} andT' = T — {a1, b1,..., bs}. Then e(G') > e(G) — (k + 2) — (k — 2) > 1 (k2 —2k — 8). Soavedeg(G') > (k2 —2k — 8)/(k+2) = k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. Then let f (a1) = u and X = V(G) \ f'(v(T')). Since dG(u) = k + 2, u hits at least s vertices in X, f is T—extensible.
2.2.2	dG(x) > k - 1
Since x = z, we consider the following two cases.
(A). x misses z. Let G' = G — {u, z, x} and T' = T — {a1, b1,..., bs, ar}. Then e(G') > e(G) — (k + 2) — (k — 5) — (k + 1) + 1 > 2(k2 — 4k — 2). Hence avedeg(G') > (k2 — 4k — 2)/(k + 1) > k — 5 and | V(T') |< k — 3. By the induction hypothesis, we have T' C G'. Since x misses z, u and dG(x) > k — 1, x misses at most two vertices of G'. If x hits f'(a2), let f (a1) = x and f (ar) = u. Since dG(x) > k — 1 and u hits all vertices of T', f is T—extensible. Hence we assume that x misses f'(a2). If x hits f'(ar-1), let
52
Ars Math. Contemp. 13 (2017) 107-123
f (ar) = x and f (ai) = u. Then f is T-extensible. If x misses f '(a2) and f '(ar-i), then x hits all of V(G') \ {f '(a2), f '(ar-i)}, because D(T) > 5, a2 and ar-i are not adjacent. Then let f (ar-i) = x, f (ai) = u, which implies that f is T-extensible. (B). x hits z. We consider the following two subcases.
(B.1). dG(x) > k - 1. Let G' = G - {u,z,x}, T' = T - {ai, bi,..., bs, ar}. Since x misses u and dG(x) > k - 1, x misses at most two vertices of G', the assertion can be proven by the similar method of (A).
(B.2). dG(x) = k - 1. Then x misses 3 vertices of V(G) \ {u}, says yi, y2, y3.
(a).	There exists one vertex yj with 1 < i < 3 such that dG(yj) > k + 1. Let G' = G - {u, z, yj, x} and T' = T - {ai, bi,..., 6s, ar-i, ci,..., ct}. Then e(G') > e(G) - (k + 2) - (k - 5) - (k + 2) - (k - 1) + 3 + 1 > ± (k2 - 6k + 4), which implies avedeg(G') > (k2 - 6k + 4)/k > k - 6 and | V(T') |< k - 4. Hence by the induction hypothesis, T' C G'. Note that yj misses at most one vertex of G'. If yj misses f'(a2), let f (ai) = u, f (ar_i) = yj; if yj misses f'(ar_2), let f (ar_i) = u,f (ai) = yj. Thus f is T-extensible.
(b).	There exists one vertex yj with 1 < i < 3 such that dG(yj) = k and yj misses z. Then the proof is similar to (a) and omitted.
(c).	There exists one vertex yj with 1 < i < 3 such that dG(yj) < k - 2. Let G' = G-{u, yj, x} andT' = T-{ai, bi,..., bs, ar}. Then e(G') > e(G)-(k+2)-(k-2)-(k-1) + 1 > 2(k2-4k-4), which implies avedeg(G') > (k2-4k-4)/(k+1) > k-5 and | V(T') |< k - 3. Hence by the induction hypothesis, T' C G'. Similarly as in case (A), there exists an embedding from T into G.
(d).	dG(yj) = k, yj hits z or dG(yj) = k - 1 for i G {1,2,3}.
(d.1). dT(ai) + dT(ar-i) > 5. Let G' = G - {u, z, yi, y2, x} and T' = T -{ai, bi,..., bs, ar-i, ci,..., ct}. Then e(G') > e(G)-(k+2)-(k-5)-(k-1)-(k-1)-(k -1) + 3 > 2 (k2-8k +10) which implies avedeg(G') > (k2 - 8k + 10)/(k -1) > k - 7 and | V(T') |< k - 5. Hence by the induction hypothesis, T' C G'. Moreover, x misses only one vertex of G'. If x misses f'(a2), let f (ai) = u, f (ar-i) = x; if x misses f '(ar-2), let f (ar-i) = u, f (ai) = x. In both situations, f is T-extensible.
(d.2). dT(ai) = dT(ar-i) = 2. Let G' = G - {u, z} and T' = T - {a0, ai}. Then e(G') > e(G) - (k + 2) - (k - 5) + 1 > ± (k2 - 2k), which implies avedeg(G') > (k2 - 2k)/(k + 2) > k - 4 and | V(T') |< k - 2. By the induction hypothesis, T' C G'. Moreover, u hits all vertices of V(G) \ {x} and z hits x. Let f (ai) = u or z and f (a0) = z or u. Then f is T-extensible.
2.3 A(G) = fc +1
Let u G V(G) be such vertex that dG(u) = k + 1 with u missing vertices xi and x2. Without loss of the generality, we can assume dG(xi) > dG(x2) and (ai) > (ar-i).
2.3.1 dT(ai) + dT(ar-1) > 5
We consider the following two cases: (A) and (B). (A). xi misses x2.
(A.1) dG(xi) + dG(x2) < 2k - 3. Let G' = G - {u,xi,x2} and T' = T -{ai, bi,..., bs}. Then e(G') > e(G) - (k +1) - (2k - 3) > i(k2 - 4k - 4), which implies avedeg(G') > (k2 - 4k - 4)/(k + 1) > k - 5 and | V(T') |< k - 3. Hence by the induction hypothesis, T' C G'. Let f (ai) = u. It is easy to see that f is T-extensible.
L.-T. Yuan andX.-D. Zhang: On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices 53
(A.2). dG(x1) + dG(X2) > 2k — 2.
(a).	dG(x1) = k — 1 Then dG(x2) = k — 1 andx1 misses {u,x2,y1,y2}. If y1,y2 = z, let G' = G — {u, z, x1,x2,y1} and T' = T — {a1,b1,... ,bs ar-1, c1,..., ct}. Then e(G') > e(G) — (k + 1) — (k — 5) — (2k — 2) — (k + 1) + 3 > ±{k2 — 8k + 8), which implies avedeg(G') > (k2 — 8k + 8)/(k — 1) > k — 7 and | V(T') |< k — 5. Hence by the induction hypothesis, T' C G'. Note that x1 misses only one vertex of G'. If x1 misses f '(a2), let f (a1) = u and f (ar-1) = x1; if x1 misses f '(ar-2), let f (ar-1) = u and f (a1) = x1. In both situations, f is T—extensible. Now assume that y1 = z or y2 = z. Let G' = G — {u, x1,x2 ,y1,y2} and T' = T — {a1,b1,..., bs,ar-1,c1,..., ct}. Then e(G') > e(G) — (k +1) — (k — 5) — (2k — 2) — (k + 1) + 2 + 1 > ± (k2 — 8k + 8), which implies avedeg(G') > (k2 — 8k + 8)/(k — 1) > k — 7 and | V(T') |< k — 5. Let f (ar-1) = u and f (a1) = x1. Then f is T—extensible.
(b).	da(x1) > k. Let G' = G — {u, z, x1, x2} and T' = T — {a1, b1,... ,bs, ar-1, c1, ..., ct}. Then e(G') > e(G) — (k + 1) — (k — 5) — (2k + 2)+ 1 + 2 > 2 (k2 — 6k + 2), which implies avedeg(G') > (k2 — 6k + 2)/k> k — 6 and | V(T') < k — 4. Hence by the induction hypothesis, T' C G'. Note that x1 misses at most one vertex of G'. If x1 misses f'(a2), let f (a1) = u and f (ar-1) = x1; if x1 misses f'(ar-2), let f (ar-1) = u and f (a1) = x1. In both situations, f is T—extensible.
(B). x1 hits x2.
(B.1). dG(x1) + dG(x2) < 2k — 2. The proof is similar to (A.1) and omitted.
(B.2). dG(x1) + dG(x2) > 2k — 1. The proof is similar to (A.2) with (a)dG(x^) = k,dG(x2) = k — 1 or k, (b)dG(x1) = k +1.
2.3.2 dT (ai) = dT (ar-1) = 2.
We consider the following four cases.
(A).	There exists a vertex v = u of degree at most k such that it hits both x1 and x2.
Let G' = G — {u, v} and T' = T — {a0, a1}. Then e(G') > e(G) — (k + 1) — k +1 > 1 (k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k — 8)/(k + 2) = k — 4 and I V(T') l< k — 2. Hence by the induction hypothesis, T' C G'. If f '(a2) hits u, let f (a1) = u. If f'(a2) misses u, then f '(a2) = x1 or x2 and let f (a1) = v, f (a0) = u. Thus f is T—extensible.
(B).	There exists a vertex v = u of degree at least k + 1 such that it hits both x1 and x2. Then dG(v) = k + 1 and v misses y1 and y2. Since the case z G {x-]_, x2,y1, y2} is much easier, we may suppose z = x1 ,x2, y1,y2. Let G' = G — {u, v, z} — x1x2 — y1y2 and T' = T — {a0,a1,ar}. Then e(G') > e(G) — 2(k + 1) — (k — 5) + 1 — 2 > 2(k2 — 4k — 4), which implies avedeg(G') > (k2 — 4k — 4)/(k + 1) > k — 5 and | V(T') l< k — 3. Hence by the induction hypothesis, T' C G'. If f '(a2) = x1 or x2, and f '(ar-1) = y1 or y2, then let f (a1) = v and f (ar) = u. If f '(a2) = x1 and f '(ar-1) = x2, then let f (a1) = v,f (ar-1) = u, because u hits all the neighbours of f'(ar-1). If f '(a2) = y1,f '(ar-1) = y2, then let f (a1) = u and f (ar-1) = v. For the rest situations, it is easy to find an embedding from T into G.
(C).	There is no vertex in V(G) \ {u} hitting both x1 and x2, and x1 misses x2. Then dG(x1) + dG(x2) < k + 1. Let G' = G — {u, x1, x2} and T' = T — {a0, a1}. Then e(G') > e(G) — (k + 1) — (k + 1) > 2(k2 — 2k — 12), Since k > 9, avedeg(G') > (k2 — 2k — 12)/(k +1) > k — 4 and | V2(T') l< k — 2. By theorem 1.7, T' C G'. Let f (a1) = u. Then f is T—extensible.
54
Ars Math. Contemp. 13 (2017) 107-123
(D). There is no vertex in V(G) \ {u} hitting both x1 and x2, and xi hits x2. Then
dG (x1) + dG(x2) < k + 3. If dG(x1) + dG(x2) < k + 2, the assertion follows from (C). Hence assume that dG(x1) + dG(x2) = k + 3. If z = x1, x2, then z has to hit x1 or x2, say that z hits x1. Let G' = G — {u, z} — x1x2 and T' = T — {ao, a1}. Then e(G') > e(G) — (k +1) — (k — 5) + 1 — 1 > 1 (k2 — 2k), which implies avedeg(G') > (k2 — 2k)/(k + 2) > k — 4 and | V(T') |< k — 2. Hence by the induction hypothesis, T' C G'. If f '(a2) hits u, let f (a1) = u; if f '(a2) = x1, let f (a1) = z and f (a0) = u. If f'(a2) = x2 and if there is a vertex w in T' such that f'(w) = x1, let f (w) = u, f (a1) = x1 and f (a0) = z, because u hits all neighbours of f'(w) in G'; if f'(a2) = x2 and there does not exist any vertex w in T' such that f '(w) = x1, let f (a1) = x1, and f (a0) = z. In all situations, f is T—extensible. If z = x1 or x2, then let G' = G — {u, z} and T' = T — {a0, a1}. Similarly, we can find an embedding from T into G.
2.4 A(G) = fc
Let u G V(G) be a vertex of degree dG(u) = k and misses three vertices x1,x2,x3. Denote by S = {x1, x2, x3}.
2.4.1	G[S] contains no edges.
Let G' = G — {u} and T' = T — {a0}. Then e(G') > e(G) — k > 1 (k2 — 8), which implies avedeg(G') > (k2 — 8)/(k + 3) > k — 3 and | V(T') |< k — 1. By the induction hypothesis, T' C G'. If f '(a1) hits u, let f (a0) = u; if f '(a1) = x,, 1 < i < 3, let f (a1) = u. Since u hits all neighbours of f '(a1) in G', f is T—extensible.
2.4.2	G[S] contains exactly one edge.
Without loss of the generality, x1 hits x2, dG(x1) > dG(x2), and dT (a1) > dT (ar-1). We consider two cases.
(A). dx(a1) + dT(ar-1) > 5.
(A.1). dG(x2) > k — 1. If x3 = z, let G' = G — {u, z, x3} — x1x2 and T' = T — {a1, b1,..., bs}. Then e(G') > e(G) — k — (k — 5) — k — 1 > 2(k2 — 4k), which implies avedeg(G') > (k2 — 4k)/(k + 1) > k — 5 and | V(T') |< k — 3. By the induction hypothesis, T' C G'. If f'(a2) hits u, then let f (a1) = u; if f'(a2) = x1 and x2 G f'(V(T')), then let f (a^ = x2; if f'(a2) = x1 and x2 G f'(V(T')) and f'(w) = x2, then let f (w) = u, f (a2) = x1, and f (a1) = x2. Hence f is T—extensible. On the other hand, if x3 = z, let G' = G — {u, z} — {x1x2} and T' = T — {a1, b1,..., bs}. Similarly, we can prove that the assertion holds.
(A.2). dG(x3) > k — 1. By (A.1), we can assume that dG(x2) < k — 2. If z = x1, x2, let G' = G — {u, z, x1, x2, x3} and T' = T — {a1, b1,..., bs, ar-1, c1,..., ct}. Then e(G') > e(G) — k — (k — 5) — (k — 2) — k — k + 2+1 > 2(k2 — 8k + 12), which implies avedeg(G') > (k2 — 8k + 12)/(k — 1) > k — 7 and | V(T') |< k — 5. Hence by the induction hypothesis, T' C G'. Moreover, x3 misses at most one vertex of V(G'). If x3 misses f '(a2), let f (a1) = u and f (ar-1) = x3; if x3 hits f '(a2), let f (ar-1) = u and f (a1) = x3. then f is T—extensible. On the other hand, if x1 = z or x2 = z, let G' = G — {u, x1, x2, x3} and T' = T — {a1, b1,..., bs, ar-1, c1,..., ct}. Using the same above argument, we can prove the assertion.
L.-T. Yuan andX.-D. Zhang: On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices 55
(A.3). dG(xi) = k,dG(x2) < k — 2 and dG(x3) < k — 2. If z = x2,x3, let G' = G — {u, z, x1; x2, x3} and T' = T — ja1, b1;..., 6s, ar_1; c1,..., ct}. Hence e(G') > e(G) — k — (k — 5) — (k — 2) — k — (k —2)+2 > 1 (k2 —8k +10), which implies avedeg(G') > (k2 — 8k + 10)/(k — 1) > k — 7 and | V(T') |< k — 5. By the induction hypothesis, T' C G'. Note that x1 misses at most one vertex in V(G'). If x1 misses /'(a2), let f (a1) = u and /(ar-1) = x1; if x1 hits /'(a2), let /(ar-1) = u and /(a1) = x1. Hence / is T—extensible. On the other hand, if x2 = z or x3 = z, let G' = G — {u, x1, x2, x3} and T' = T — {a1, b1,..., 6s, ar-1, c1,..., ct}. By the same above argument, we can prove the assertion.
(A.4). dG(x1) < k — 1,dG (x2) < k — 2 and dG(x3) < k — 2. Then there exists a vertex u' in V(G) \ {x1, x2, x3, u} with degree at least k — 1. Otherwise, by ¿(G) < k — 5, we have avedeg(G) < k+(k_1)(k_2)+(k_1)+2(fc_2)+(fc_5) < k — 2, which is a contradiction. Let G' = G — {u, u'} — {x1x2} and ++' = T — {ab b1,..., bs}. Then e(G') > e(G) — k — k + 1 — 1 > 1 (k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k — 8)/(k + 2) = k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. If /'(a2) hits u, let /(a1) = u; if /'(a2) misses u, let /(a2) = u and /(a1) = u'. Then / is T—extensible.
(B). dT (a1) = 2 and dT (ar_1) = 2. If there exists a vertex w that hits both x1 and x3, let G' = G — {u, w} — x1x2 and T' = T — {a0, a1}. Then e(G') > e(G) — 2k + 1 — 1 > 1 (k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k + 8)/(k + 2) = k — 4 and I V(T') |< k — 2. By the induction hypothesis, T' C G'. If /'(a2) = x1 or x3, let /(a1) = w and /(a0) = u; if /'(a2) = x2 and x1 G /'(V(T')), let /(a1) = x1 and /(ao) = w; if /'(«2) = x2 and x1 G /'(V(T')),/'(v) = x1, let /(v) = u, /(«1) = x1 and /(a0) = w. In the above situations, / is T—extensible. On the other hand, if there is no vertex hits both x1 and x3,or x2 and x3. then dG(x1)+dG(x3) < k, dG(x2)+dG(x3) < k. Since dG(xj) > |_|J and k > 9, dG(x4) < k — 2. Hence, similarly as in (A.4), there exists a vertex u' in V(G) \ {x1, x2, x3, u} with degree at least k — 1, and an embedding of T into G.
2.4.3 G[S] contains exactly two edges
Without loss of the generality, assume that x1 hits both x2 and x3. We consider the following two cases.
(A).	dT(a1) = 2. Let G' = G — {u,x1} and T' = T — {a0,a1}. Then e(G') > e(G) — 2k > 1 (k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k — 8)/(k + 2) > k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. If /'(«2) = x2 or x3 (say x2), let /(«1) = x1; Moreover, if x3 / /'(V(T')), let /(«0) = x3; if x3 G /'(V(T')) and /'(v) = x3, let /(v) = u, /(«1) = x1, and /(«0) = x3. Hence, / is T-extensible. If /'(«2) = x2, x3, then it is easy to find an embedding from T to G.
(B).	dT(«1) > 3.
(a). dG(x1) > k — 1. If z = x2,x3, let G' = G — {u,z,x1} and T' = T — {«1, b1,..., bs}. Then e(G') > e(G) — k — (k — 5) — k +1 > 2(k2 — 4k + 4), which implies avedeg(G') > (k2 — 4k + 4)/(k +1) > k — 5 and | V(T') |< k — 3. By the induction hypothesis, T' C G'. If /'(«2) = x2 or x3 (say x2), let /(«1) = x1. Moreover, if x3 G /'(V(T')), let /(61) = x3; if x3 G /'(V(T')) and /'(v) = x3, let /(v) = u, /(«1) = x1 and /(61) = x3. Because u hits all neighbours of /'(v) and dG(x1) > k — 1, / is T—extensible. If /'(«2) = x2, x3, it is easy to find an embedding from T to G. On the other hand, if z = x2 or x3 (say x2), let G' = G — {u, x1, x2}, by the
56
Ars Math. Contemp. 13 (2017) 107-123
same argument above, the assertion holds.
(b).	dG(xi) < k — 2, dG(x2) = k or dG(x3) = k (say dG(x2) = k). Then there exists a vertex y G V(G) \ {u, x1,x2,x3} such that x2 misses y. So x2 misses u, x3 and y and u misses x3. By Case 2.4.2, we can assume y hits x3. Further, by (a), we can assume dG(y) < k — 2. If z = x1,y, let G' = G — {u, z, x2, x3, y} and T' = T — {a1, b1,..., 6s, ar-1, c1,..., ct}. Then e(G') > e(G) — k — (k — 5) — k — k — (k — 2) + 3 > 2(k2 — 8k + 12), which implies avedeg(G') > (k2 — 8k + 12)/(k — 1) > k — 7 and | V(T2') |< k — 5. By the induction hypothesis, T' C G'. Further, if f >2) = x1, let f (a1) = x2 and f (ar-1) = u; if f'(ar-2) = x1, let f (ar-1) = x2 and f (a1) = u. Hence f is T—extensible. On the other hand, if z = y, let G' = G — {u, x2, x3, y} and T' = T — {«1,61,..., bs, ar_1, C1,..., ct}; if z = x1, let G' = G — {u, z, x2, x3, y} and T' = T — {a1, 61,..., 6s, ar-1, c1,..., ct}. Then by the same argument, it is easy to prove that the assertion holds.
(c).	dG(x1) < k — 2, dG(x2) = k — 1 and dG(x3) = k — 1. Let G' = G — {u, x2, x3} andT' = T — {«4,61,..., 6s}. Then e(G') > e(G)—k — (k — 1) —(k — 1) > 1(k2 —4k—4), which implies avedeg(G') > (k2 — 4k — 4)/(k +1) > k — 5 and | V(T') |< k — 3. Bythe induction hypothesis, T' C G'. If f'(a2) = x1, let f (a1) = x2, which f is T—extensible. If f '(a2) = x1, it is easy to find an embedding from T to G.
(d).	dG(x1) < k — 2, and dG(x2) < k — 2 or dG(x3) < k — 2 (say dG(x2) < k — 2), hence dG(x3) < k — 1 by (b). Then there exists a vertex u' G V(G) \ {x1,x2,x3,u} of degree at least k — 1, otherwise 2e(G) < (k — 1)(k — 2) + (k — 5) + k + 2(k — 2) + (k — 1) < (k + 4)(k — 2) which is impossible. Let G' = G — {u,u',x1} and T' = T — {a1, 61,..., 6s}. Then e(G') > e(G) — 2k — (k — 2) + 1 > 1 (k2 — 4k — 2), which implies avedeg(G') > (k2 — 4k — 2)/(k +1) > k — 5 and | V (T') |< k — 3. Bythe induction hypothesis, T' C G'. Hence if f'(a2) hits u, let f (a1) = u; if f'(a2) = x2 or x3 (say x2), let f (a2) = u and f (a1) = u' since u hits all the neighbours of f'(a2). Then f is T—extensible.
2.4.4 G[S] contains exactly three edges
The following two cases are considered.
(A).	dT (a1) = 2. If there exists an 1 < i < 3 (say i = 1) such that dG(x1) < k — 1, let G' = G — {u,x1}— x2x3 and T' = T — {a0, a1}. Then e(G') > e(G) — k — (k — 1) — 1 > 1 (k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k — 8)/(k + 2) = k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. If f'(a2) = x2 or x3 (say x2), let f (a1) = x1. Moreover, if x3 G f'(V(T')), let f (ao) = x3; and if x3 G f'(V(T')) and f'(v) = x3, let f (v) = u, f (a1) = x1, f (a0) = x3. Hence f is T—extensible. On the other hand, if dG(x1) = dG(x2) = dG(x3) = k, let G' = G — {u, x1} and T' = T — {a0, a1}. Then e(G') > e(G)—2k > 2 (k2 —2k — 8), which implies avedeg(G') > (k2 —2k — 8)/(k+2) = k — 4 and | V(T') |< k — 2. By the induction hypothesis,T' C G'. If f'(a2) = x2 or x3, let f (a1) = x1; if f'(a2) = x2, x3, let f (a1) = u. Hence f is T-extensible.
(B).	dT(a1) > 3. If there exists an 1 < i < 3 (say i = 1) such that dG(x1) > k — 1, Let G' = G — {u,z,x1}— x2x3. By the same argument as Case 2.4.3.(B).(a), the assertion holds. The rest is similar as Case 2.4.3.(B).(d).
L.-T. Yuan andX.-D. Zhang: On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices 57
2.5 A (G) = k - 1
Since A(G) = k - 1 and ¿(G) < k - 5, there exist at least four vertices of degree k - 1. Otherwise 2e(G) < 3(k-1)+k(k-2) + (k - 5) = (k-2)(k+4), which is a contradiction. Let ui be vertex of da(ui) = k - 1 missing four vertices of Si = {x^, xi2, xi3, xi4} for i = 1,2, 3,4. If there exists a vertex ui with 1 < i < 4 such that G[Si] contains at most one edge. Let G' = G - {ui} - E(G[Si]) and T' = T - {ao}. Then e(G') > e(G) - (k - 1) - 1 > I(k2 - 8), which implies avedeg(G') > (k2 - 8)/(k + 3) > k - 3 and | V(T') |< k - 1. By the induction hypothesis, T' Ç G'. If ui hits f '(a1), let f (a0) = ui, and if ui misses f '(a1 ), let f (a1) = ui. Then f is T-extensible. Hence we assume that G[Si] contains at least two edges for i = 1, 2, 3,4.
2.5.1 dT(at) > 3, dT(ar-1) > 2
We consider the number of the edges in G[«i, u2, «3, «4].
(A).	G[u1, u2, «3, u4] contains at least one edge, say u1 hits u2. If z G = {x11, x12, x13,x14}, let G' = G - {u1,u2,z} - E(G[S1]) and T' = T - {a1, b1,..., bs}. Then e(G') > e(G) - 2(k -1) - (k - 5) + 1 - 6 > ± (k2 - 4k - 4), which implies avedeg(G') > (k2 - 4k - 4)/(k +1) > k - 5 and | V(T ) |< k - 3. By the induction hypothesis, T' C G'. Hence if u1 hits f'(a2), let f (a1) = u1; and if u1 misses f '(a2), let f (a2) = u1 and f (a1) = u2. Since u1 hits all the neighbours of f '(a2) in G', f is T-extensible. On the other hand, if z G S1 = {x11, x12, x13, x14}, say z = x11. Let G' = G - {u1, u2, z} -E(G[x12, x13, x13]). By the same argument, the assertion holds.
(B).	G[u1, u2, u3, u4] contains no edges.
(B.1). If there exist two vertices, say u1 and u2, in {u1, u2, u3, u4} such that u1 misses y1 and u2 misses y2, where y1 = y2 and y1,y2 G {« , ...,«4}. Let G' = G - {«1, «2, «3, «4} and T' = T - {01, 61,..., 6s, ar_1, C1,..., ct}. Then e(G') > e(G) - 4(k - 1) > 1 (k2 - 6k), which implies avedeg(G') > (k2 - 6k)/k = k - 6 and | V(T') |< k - 4. By the induction hypothesis, T' C G'. Hence if f'(«2) = y1, let f («1) = «2 and f (ar_1) = «1; if f '(«2) = y2, let f («1) = «1 and f (ar_1) = «2. Moreover, if f '(ar_2) = y1, let f (a1) = «1 and f (ar-1) = «2; and if f '(ar_2) = y2, let f (a1) = «2 and f (ar-1) = «1. Therefore, f is T-extensible.
(B.2). There exist a vertex y G {«1,..., «4} such that y misses «1,..., «4. Then G[«1,..., «4, y] contains no edges.
(a).	dT(ar-1) = 2. Then there exists a vertex w hits {«1, «2, «3, w4} and y. Let G' = G-{«1,w} andT' = T-{ar-1,ar}. Then e(G') > e(G)-2(k-1) + 1 > 2(k2-2k-2), which implies avedeg(G') > (k2 - 2k - 2)/(k + 2) > k - 4 and | V(T') |< k - 2. By the induction hypothesis, T' C G'. Hence if f '(ar_2) = «2, «3, «4 or y, let f (ar-1) = w and f (ar) = «1; and if f'(ar_2) = «2, «3, «4, y, let f (ar_1) = «1 and f (ar) = w. Therefore f is T-extensible.
(b).	dT(ar_1) > 3. If z = y, let G' = G - {«1, «2, «3, «4, y, z} and T' = T -{a1,61, ...,6s,ar_1,c1,.. .,ct}. Then e(G') > e(G) - 4(k - 1) - (k - 1) - (k - 5)+4 > 1 (k2 - 10k + 20), which implies avedeg(G') > (k2 - 10k + 20)/(k - 2) > k - 8 and I V(T') |< k - 6. By the induction hypothesis, T' C G'. Let f («1) = «1 and f (ar _ 1) = «2. Then f is T-extensible. On the other hand, if z = y, let G' = G - {«1, «2, «3, «4, z} and T' = T-{a1, 61,..., 6s, ar _ 1, c1,..., ct}. By the same argument, the assertion holds.
58
Ars Math. Contemp. 13 (2017) 107-123
2.5.2 dT(a1) = 2, dT(ar-1) = 2.
We will discuss the following four cases: (A), (B), (C) and (D).
(A).	There exists a 1 < i < 4, say i = 1, such that G[S1] contains two or three edges. If mi hits one vertex, say u2, of three vertices u2, u3, u4. Let G' = G — {u1, u2} — E(G[S1]) and T' = T — {a0, a1}. Then e(G') > e(G) — 2(k — 1) + 1 — 3 > 2(k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k — 8)/(k + 2) = k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. Hence if u1 hits /'(a2), let / (a1) = u1; and if u1 misses / '(a2), let /(a2) = u1 and /(a1) = u2. Since u1 hits all the neighbours of /'(a2) in G', / is T—extensible. Therefore, we assume that u1 misses uj for j = 2, 3,4. Then u1 misses x11 = u2,x12 = u3, x13 = u4, x14 and G[u2, u3, u4, x14] contains two or three edges.
(A.1). x14 hits one vertex, say u2, of three vertices u2,u3,u4. Let G' = G — {u1, u2,u3,u4} and T' = T — {a0, a1, ar-1, ar}. Then e(G') > e(G) — 4(k — 1) > 1 (k2 — 6k), which implies avedeg(G') > (k2 — 6k)/k = k — 6 and | V(T') |< k — 4. By the induction hypothesis, T' C G'. Since G[m2, u3, u4, x14] contains two or three edges, there exists a vertex, say u3, of two vertices u3,u4 misses at most one vertex, say y1, in V(G) \ {u1,u2,u4, x14}. Hence if /'(a2) = x14 or y1, and /'(ar-2) = y1 or x14, let /(a1) = u2 or u1 and /(ar-1) = u1 or u2, then / is T—extensible. For the rest cases, it is easy to find an embedding from T to G.
(A.2). x14 misses three vertices u2, u3, u4. Then G[u2, u3, u4] contains two or three edges. We can assume that u2 hits u3 and u4. If u3 misses u4, u3 misses at most one vertex, says y1, in V(G) \ {u1, u2, u4, x14}. Then let G' = G — {u1, x14, u3, u4} and T' = T — {a0, a1, ar-1, ar}. By the similar argument as Case (A.1), the assertion holds. Hence we can assume that u3 hits u4 and u3 misses z1, z2, u1, x14. Let G' = G — {u1, x14, u3, u4} — {z1z2} and T' = T — {a0, a1, ar-1, ar}. Then e(G') > e(G) — 4(k — 1) + 1 — 1 > 1 (k2 — 6k), which implies avedeg(G') > (k2 — 6k)/k = k — 6 and | V(T') |< k — 4. By the induction hypothesis, T' C G'. Hence if /'(a2) = z1 or z2, and /'(ar-2) = z2 or z1, let /(a2) = u3, /(a1) = u4, /(ar-1) = u1. Therefore / is T — extensible. If /'(a2) = z1 or z2, and /'(ar-2) = u2, let /(a1) = u1, /(ar-1) = u4. Therefore / is T — extensible. For the rest cases, it is easy to find an embedding from T to G.
(B).	There exists a 1 < i < 4, say i =1, such that G[S1] contains exactly four edges.
(B.1). There exists a vertex, say x11, of degree 3 in G[S1] and | E(G[S1]) |< 5.
Then x11 hits x12,x13 and x14. Let G' = G — {u1,x11} — E(G[x12, x13,x14]) and T' = T — {a0, a1}. Then e(G') > e(G) — 2(k — 1) — 2 > 2(k2 — 2k — 8), which implies avedeg(G') > (k2 — 2k — 8)/(k + 2) = k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. Hence if u1 hits /'(a2), let /(a1) = u1, which implies that / is T—extensible. If u1 misses /'(a2) and /'(a2) = x12, let /(a1) = x11. Moreover, if x13 or x14 ^ /'(V(T')), then let /(a0) = x13 or x14. Then / is T—extensible. If x13 and x14 € /'(V(T')), /'(w) = x13 or x14, let /(w) = u1, /(a0) = x13 or x14. Then / is T—extensible. For the rest cases, it is easy to find an embedding from T to G.
(B.2). The degree of every vertex in G[S1] is two. We assume that x11 hits x12, x12 hits x13, x13 hits x14, x14 hits x11.
(a). u1 hits all vertices of {u2, u3, u4}.
(a.1). There exists a vertex uj, say u2, in {u2, u3, u4} which misses x11, x12, x13 and x14. Let G' = G — {u1, U2, in, x12} — x13x14 and T' = T — {a0, a1, ar-1, ar}. Then e(G') > e(G) — 4(k — 1) + 1 > 1 (k2 — 6k + 2), which implies avedeg(G') > (k2 — 6k + 2)/k > k — 6 and | V(T') |< k — 4. By the induction hypothesis, T' C G'. If /'(a2) = x13, /'(ar-2) = x14, let /(a1) = x12, /(a0) = xn, /(a^) = U1, /(ar-1) =
L.-T. Yuan andX.-D. Zhang: On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices 59
u2. Since mi hits all the neighbours of f '(ar-2) in G', f is T-extensible. For the rest cases, similarly, it is easy to find an embedding from T to G.
(a.2). There exists a vertex, say u2, in {u2, u3, u4} such that it hits at least two vertices of {in, X12, X13, X14}, say u2 hits in and X13, or u2 hits in and xi2.
If «2 hits in and X13, let G' = G — {«1,«2} — X11X12 — X12X13 — X13X14 and T' = T — {a0, a1}. Then e(G') > e(G) — 2(k — 1) + 1 — 3 > 2(k2 — 2k — 8), which implies avedeg(G') > k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. Hence if f'(a2) = X11 or X13, let f (a1) = u2; if f'(a2) = X12, let f (a2) = u1 and f (a1) = «2; if f'(02) = X14 and X13 G f'(V(T')), let f (04) = X13 and f (ao) = «2; if f'(02) = X14 and X13 G f'(V(T')), let f (v) = «1,f (01) = X13,f (ao) = «2, because there is a vertex v, f '(v) = X13 and u1 hits all the neighbours of f'(v) in G'. Therefore f is T—extensible.
If «2 hits X11 and X12, let G' = G — {«1,«2} — X12X13 — X13X14 — X11X14 and T' = T — {a0,a1}. Then e(G') > e(G) — 2(k — 1) + 1 — 3 > 2(k2 — 2k — 8), which implies avedeg(G') > k — 4 and | V(T') |< k — 2. By the induction hypothesis, T' C G'. Hence if f'(a2) = X11 or X12, let f (a1) = u2; if f'(a2) = X13 or X14, let f (a2) = u1, f (a1) = u2, because u1 hits all the neighbours of f'(a2) in G'. Therefore f is T—extensible.
(a.3). ui hits exactly one vertex of {x11, x12, x13, x14} for i = 2,3,4.
(i).	There exist two vertices of {u2,u3,u4} such that they hit the same vertex in
{x11, X12, x13, x14}, says both u2 and u3 hit x14.
If u2 and u3 misses the same vertices, say, {x11, x12, x13, y}, then u2 hits u3. Further, if G[x11, x12, x13, y] contains at most three edges or has a vertex of degree 3, the assertion follows from Case 2.5.2.(A) or Case 2.5.2.(B.1). Therefore we can assume that y hits both X11 and X13. Let G' = G — {«2, «3, X11, X12} — X13y and T' = T — {ao, 01, ar-1, ar}. The assertion follows from Case 2.5.2. (B.2).(a.1).
If m2 misses {x11, x12, x13, y1} and u3 misses {x11, x12, x13, y2} with y1 = y2, let G' = G — {«1, «2,«3,X14} — X11X12 — X12X13 and T' = T — {ao, 01, ar-1, ar}. Then e(G') > e(G) — 4(k —1) + 4 — 2 > 2 (k2 — 6k + 4), which implies avedeg(G') > k — 6 and | V(T') |< k — 4. By the induction hypothesis, T' C G'. Hence if f '(02) = X11 or X13, let f (01) = X14,f (ao) = «3 or «2 or let f (02) = «1,f (01) = «3 or «2. If f'(02) = X12, let f (02) = «1,f (01) = «3 or «2. If f'(02) = y1 or y2, let f (01) = «3 or «2. Since there is a choice which uses distinct vertices of {u1, u2, u3, x14} for any two vertices of {x11, x12, x13, y1, y2}, we can find an embedding from T to G. (For example, if f '(a2) = X11,f'(ar-2) = X13, let f (01) = X14,f (ao) = «3,f (0^-2) = «1,f (0^-1) = «2.)
(ii).	{u2,u3,u4} hits the different vertices of {x11, x12,x13, x14}. Without loss of generality, we assume that u2 hits x11 and u3 hits x13, u2 misses y1 and u3 misses y2. Let G' = G — {«1, «2,«3,X13} — X11X12 — X11X14 and T' = T — {ao, 01, ar-1, ar}. Then e(G') > e(G) — 4(k —1) + 3 + 0 — 2 > 2 (k2 — 6k + 2), which implies avede-(G') > k — 6 and | V(T') |< k — 4. By the induction hypothesis, T' C G'. Hence if f'(02) = X12 or x14, let f (a1) = x13 and f (ao) = u3, or let f (a2) = u1 and f (a1) = u2, if f '(a2) = y1 or y2, let f (a1) = u1, if f'(a2) = x11, let f (a1) = u2, Therefore f is T—extensible. For the rest cases, by the same argument, it is easy to find an embedding from T to G.
(b). u1 hits one or two vertices of {u2,u3,«4}. Without loss of the generality, we assume that u1 hits u2 and u1 misses u4. Then u4 G {x11, x12, x13, x14}, say u4 = x14, u4 misses u1,x12,z1,z2.
If «2 = Z1, Z2, then «2 hits «4. Let G' = G — {«1, «2, «4, X12} — Z1Z2 and T' =
60
Ars Math. Contemp. 13 (2017) 107-123
T - ja0, a1, ar_i, ar}. Then e(G') > e(G) - 4(k - 1) + 2 - 1 > ± (k2 - 6k), which implies avedeg(G') > k - 6 and | V(T') |< k - 4. By the induction hypothesis, T' C G'. Hence if f '(a2) = x11 and f '(ar_2) = x13, let f (a1) = «4,f(ar_2) = u1 and f(ar_1) = «2, if f'(a2) = Z1 and f'(ar_2) = Z2, let f(a1) = «1,/(ar_2) = «4 and f (ar_1) = u2. Therefore f is T-extensible. For the rest cases, it is easy to find an embedding from T to G. If u2 = z1 or z2, say u2 = z1, let G' = G - {u1, u2, u4, x12} and T' = T - {ao , a1, ar_1, ar }. This situation is much easier than the above case.
(c). u1 misses all the vertices of {u2, u3, u4}. Without loss of generality, we assume «2 = xn, «3 = X12, «4 = X13. Let «2 miss {«1,^13,^1,^2}. If G[«1, X13,y1,^2] contains two, or three edges, or a vertex of degree 3, the assertion follows from Case 2.5.2 (A). and Case 2.5.2 (B.1). Hence we assume that «1 hits y1, y1 hits «4 = x13, «4 hits y2 and y2 hits «1. Hence the assertion follows from Case 2.5.2. (B.2). (a) and Case 2.5.2. (B.2).(b).
(C).	There exists a 1 < i < 4, say i = 1, such that G[x11, x12, x13, x14] contains five edges. Then we assume that x11 hits x12, x13 and x14. Let G' = G - {«1, x11} -E(G[x12, x13, x14]) and T' = T - {a0, a1}. The assertion follows from the proof of Case 2.5.2 (B.1).
(D).	There exists a 1 < i < 4, say i = 1, such that G[x11, x12, x13, x14] contains six edges. If dG(x11) < k - 2, similar as Case 2.5.2 (B.1), we can prove the assertion. So we can assume dG(x 11) = dG(x12) = dG(x13) = dG(x14) = k - 1, we can also assume if dG(x) = k - 1, and x misses y then dG(y) = k - 1, furthermore we can assume x hits all of the vertices whose degree is less than k - 1. Let G' = G - {«1, z}, z hits all of {x1, x2, x3, x4}, T' = T - {a0, a1}. So e(G') > e(G) - (k - 1) - (k - 5) + 1 > 2(k2 - 2k + 6). avedeg(G') > (k2 - 2k + 6)/(k + 2) > k - 4 and | V(t') |< k - 2. By the induction assumption, T' C G'. If f'(a2) hits «1, then f (a1) = «1, f (a0) = z. If f '(a2) misses «1, then f (a0) = «1, f (a1) = z. f is T-extensible.
References
[1]	S. Balasubramanian and E. Dobson, Constructing trees in graphs with no k2,s, Journal of Graph Theory 56 (2007), 301-310, http://dx.doi.org/10.1002/jgt.20261.
[2]	S. Brandt and E. Dobson, The Erd6s-S6s conjecture for graphs of girth 5, Discrete Math. 150 (1996), 411-414, selected papers in honour of Paul Erdos on the occasion of his 80th birthday (Keszthely, 1993), http://dx.doi.org/10.1016/0012-365X(95)00207-D.
[3]	E. Dobson, Constructing trees in graphs whose complement has no K2,s, Com-bin. Probab. Comput. 11 (2002), 343-347, http://dx.doi.org/10.1017/ S0963548302005102.
[4]	N. Eaton and G. Tiner, On the Erdos-Sos conjecture and graphs with large minimum degree, Ars Combin. 95 (2010), 373-382.
[5]	P. Erd6s, Some problems in graph theory, Theory of Graphs and Its Applications (1965), 29-36.
[6]	P. ErdSs and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar 10 (1959), 337-356 (unbound insert).
[7]	G. Fan, The Erdos-Sos conjecture for spiders of large size, Discrete Math. 313 (2013), 25132517, http://dx.doi.org/10.1016/j.disc.2013.07.021.
[8]	G. Fan and L. Sun, The Erd6s-S6s conjecture for spiders, Discrete Math. 307 (2007), 30553062, http://dx.doi.org/10.1016/j-disc.2007.03.018.
L.-T. Yuan andX.-D. Zhang: On the Erdos-Sos Conjecture for graphs on n = k + 4 vertices 61
[9] P. E. Haxell, Tree embeddings, J. Graph Theory 36 (2001), 121-130, http://dx.doi. org/10.1002/10 97-0118(200103)36:3<121::AID-JGT1000>3.0.œ;2-U.
[10]	A. McLennan, The Erdos-Sos conjecture for trees of diameter four, J. Graph Theory 49 (2005), 291-301,http://dx.doi.org/10.1002/jgt.20083.
[11]	J.-F. Sacie and M. WoZniak, The Erdos-Sos conjecture for graphs without C4, J. Combin. Theory Ser. B 70 (1997), 367-372, http://dx.doi.org/10.100 6/jctb.19 97.1758.
[12]	A. F. Sidorenko, Asymptotic solution for a new class of forbidden r-graphs, Combinatorica 9 (1989), 207-215, http://dx.doi.org/10.1007/BF0212 4 681.
[13]	P. J. Slater, S. K. Teo and H. P. Yap, Packing a tree with a graph of the same size, J. Graph Theory 9 (1985), 213-216, http://dx.doi.org/10.1002/jgt.319009020 3.
[14]	G. Tiner, On the Erdôs-Sos conjecture for graphs on n = k + 3 vertices, Ars Combin. 95 (2010), 143-150.
[15]	M. Wang, G.-j. Li and A.-d. Liu, A result of Erdfis-Sos conjecture, Ars Combin. 55 (2000), 123-127.
[16]	M. WoZniak, On the Erdos-Sos conjecture, J. Graph Theory 21 (1996), 229234, http://dx.doi.org/10.10 02/(SICI)1097-0118(199602)21:2<229:: AID-JGT13>3.3.CO;2-2.
[17]	B. Zhou, A note on the Erdos-Sos conjecture, Acta Math. Sci. (English Ed.) 4 (1984), 287-289.