The Ramsey number r(K5 - P3,K5)

The Ramsey number r(K5−P3, K5) Luis Boza∗ Departamento de Matem´atica Aplicada I Universidad de Sevilla, Seville, Spain [email protected] Submitted: Dec 2, 2010; Accepted: Apr 4, 2011; Published: Apr 14, 2011 Mathematics Subject Classification: 05D10 Abstract For two given graphs G1and G2, the Ramsey number r(G1, G2) is the smallest integer nsuch that for any graph Gof order n, either Gcontains G1or the complement of Gcontains G2. Let Kmdenote a complete graph of order mand Kn−P3a complete graph of order nwithout two incident edges. In this paper, we prove that r(K5−P3, K5) = 25 without help of computer algorithms. 1 Introduction All graphs considered in this paper are simple graphs without loops. For two given graphs G1and G2and a given integer n, let R(G1, G2;n) denote the set of all graphs Gof order n, such that Gdoes not contain G1and Gdoes not contain G2, where Gis the complement of G. The Ramsey number r(G1, G2) is the smallest integer nsuch that R(G1, G2;n) is empty. The values of r(G1, G2) for all graphs G1and G2of order at most five up to the three cases that G1is one of the graphs K5−P3,K5−eand K5and G2=K5are found in [1, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 17, 18]. Kalbfleisch [13] proved that r(K5−P3, K5)≥25 and McKay and Radziszowski [15] found 350904 graphs belonging to R(K4, K5; 24) ⊆R(K5−P3, K5; 24), but there might be more of them. Recently, Black, Leven and Radziszowski [2] proved that r(K5−P3, K5)≤ 26 and Clavert, Schuster and Radziszowski [4] computed the main result of the present paper. ∗This research is supported by the Andalusian Government under project P06-FQM-01649. 1 2 Main result In this paper we find the value of r(K5−P3, K5) without help of computer algorithms. The main result is the following: Theorem 2.1 r(K5−P3, K5) = 25. In order to prove Theorem 2.1, we proceed by reduction to the absurd. Suppose that there exists a graph G∈R(K5−P3, K5; 25). Since r(K4, K5) = 25 [15] we have Gcontains K4. Let Kbe the set of cliques of Gof order 4, let K∈ K be such that Pv∈V(K)d(v) = max{Pv∈V(X)d(v) : X∈ K} and let v1,v2,v3and v4be the vertices of K. We may suppose without loss of generality that d(v1)≥d(v2)≥d(v3)≥d(v4). Let |A|denote the cardinality of the set A. If Fis a graph then V(F) denotes its vertex set. The neighborhood NF(v) of a vertex vis the set of vertices adjacent to vin the graph F. If G1is isomorphic to a subgraph of G2then we use G1⊆G2to denote it. If Ais a subset of V(F), then F[A] is the subgraph induced by A. If v∈V(F), dF(v) is the degree of vin F. The maximum and minimum degree of Fare denoted by ∆(F) and δ(F), respectively. Let d,Vand Ndenote dG,V(G) and NG, respectively. If kis a positive integer, F∈R(Km−P3, Kn;k) and v∈V(F) then F[NF(v)] ∈ R(Km−1−P3, Kn;dF(v)) and F[NF(v)] ∈R(Km−P3, Kn−1;k−1−dF(v)). Thus ∆(F)≤ r(Km−1−P3, Kn)−1 and δ(F)≥k−r(Km−P3, Kn−1). Since r(K5−P3, K4) = 18 [7] we have δ(G)≥7. In the rest of the paper, iand jare two different integers with 1 ≤i, j ≤4. Let Ai=N(vi)−V(K) and D=V(G)−V(K)−S4 k=1 Ak.Ai∩Aj=∅, because in otherwise Gshould contain K5−P3. Hence {V(K), A1, A2, A3, A4, D}is a partition of V. Obviously, |Ai|=d(vi)−3≥4. If u∈Aior u∈Dthen |N(u)∩Ai|, the number of vertices belonging to Ajadjacent to u, is denoted by ej(u). Let Hidenote the graph G[V(G)−(Ai∪V(K))] = G[NG(vi)]. Clearly Hi∈R(K5− P3, K4; 21 − |Ai|). If u∈V−V(K)−D,g(u) will represent the integer kfor which u∈Ak. Also, if u∈D, we define g(u) = 0. In order to prove Theorem 2.1, we need the following results: Lemma 2.1 Let u∈Aiand w∈D. Then d(u)−9≤ej(u)≤d(u) + |Aj| − 13 and d(w)−8≤ei(w)≤d(w) + |Ai| − 12. Proof. Since Hj∈R(K5−P3, K4; 21−|Aj|), r(K4−P3, K4) = 9 [6] and r(K5−P3, K3) = 9 [7], we have dHj(u), dHj(w)≤∆(Hj)≤r(K4−P3, K4)−1 = 8 and dHj(u), dHj(w)≥ δ(Hj)≥21 − |Aj| − r(K5−P3, K3) = 12 − |Aj|. The results follow on noting that d(u) = dHj(u) + ej(u) + 1 and d(w) = dHi(w) + ei(w). Corollary 2.1 Let kbe, with 1≤k≤4and k6=i, and let u∈Ai. Then ej(u)+4−|Aj| ≤ ek(u). 2 Proof. The result is obtained from ej(u)≤d(u) + |Aj| − 13 and d(u)−9≤ek(u). Corollary 2.2 The degree in Gof every vertex of Dis 10. Proof. Let w∈D. Since d(w) = dD(w) + P4 k=1 ek(w), by Lemma 2.1, we have dD(w) + 4(d(w)−8) ≤d(w)≤dD(w) + P4 k=1(d(w) + |Ak| − 12). Thus 3d(w)≥48 −P4 k=1 |Ak| − dD(w)≥48−P4 k=1 |Ak|−(|D|−1) = 28 and 3d(w)≤32−dD(w)≤32. As 28 ≤3d(w)≤ 32, the result follows. Lemma 2.2 The vertices of degree 7or 8in Gbelong to K. Proof. Let u∈V(G)−V(K). On the one hand, if u∈Dthen, by Corollary 2.2, d(u) = 10, thus d(u)≥9. On the other hand, if u∈Aithen, by Lemma 2.1, d(u) = 1+dG[Ai](u)+|D∩N(u)|+P4 k=1,k6=iek(u)≤1+(|Ai|−1)+|D|+P4 k=1,k6=i(d(u)+|Ak|−13) = 3d(u) + P4 k=1 |Ak|+|D| − 39 = 3d(u) + 21 −39. Therefore d(u)≥9. Corollary 2.3 Ghas exactly one subgraph isomorphic to K4. Proof. Suppose, to the contrary, that there exists K′∈ K − {K}. Since K5−P3*G, we have |V(K)∩V(K′)| ≤ 1 and, by Lemma 2.2, there are at least three vertices in K′ with degree in Gat least 9. Thus Pv∈V(K′)d(v)≥3·9 + 1 ·7 = 34. As 21 ≥P4 k=1 |Ak|= P4 k=1(d(vk)−3), we have P4 k=1 d(vk)≤33, contradicting the definition of K. Corollary 2.4 Let u∈V−V(K), then K3*G[N(u)]. Proof. If there is a clique of order 3 in G[N(u)], let u1,u2and u3be its vertices. G[{u, u1, u2, u3}] is a subgraph of Gdifferent of Kisomorphic to K4, contradicting Lemma 2.3. Corollary 2.5 G[Ai]∈R(K3, K4;|Ai|). Proof. If K3⊆G[Ai], then let u1,u2and u3be the vertices of a clique of order 3 of G[Ai]. G[{u1, u2, u3, vi}] is a subgraph of Gisomorphic to K4different from K, contradicting Corollary 2.3. If K4⊆G[Ai], then let u1,u2,u3and u4be the four vertices of a clique of order 4 of G[Ai]. G[{u1, u2, u3, u4, vj}] is a subgraph of Gisomorphic to K5, a contradiction. Thus G[Ai]∈R(K3, K4;|Ai|). Corollary 2.6 Hi∈R(K4, K4; 21 − |Ai|). Proof. Kis not a subgraph of Hi, thus, by Corollary 2.3, K4*Hi. Since Hi∈R(K5− P3, K4; 21 − |Ai|) we have K4*Hi, concluding the proof. Lemma 2.3 D=∅. 3 Proof. Suppose, to the contrary, that there exists w∈D. Let X=V(G)−V(K)− N(w)− {w}. Since N(w)∩V(K) = ∅, and, by Corollary 2.2, |N(w)|= 10, we have |X|= 25 −4−10 −1 = 10. As Kis not a subgraph of G[X], by Corollary 2.3, K4* G[X] = G[X]. r(K3, K4) = 9 [10], thus R(K3, K4; 10) = ∅and G[X]/∈R(K3, K4; 10), hence K3⊆G[X]. Let u1,u2and u3be the vertices of a clique of order 3 of G[X] and let k∈ {1,2,3,4}−{g(u1), g(u2), g(u3)}. Then G[{w, vk, u1, u2, u3}]⊆Gis isomorphic to K5, a contradiction. Lemma 2.4 If G[Ai]contains a clique of order 3, with vertices w1,w2and w3, then |(N(w1)−N(w2)−N(w3)) ∩V(Hi)| ≤ 2. Proof. Let Y= (N(w1)−N(w2)−N(w3)) ∩V(Hi). By Corollary 2.4, K3*G[Y]⊆ G[N(w1)]. If K2⊆G[Y] then let u1u2be an edge of G[Y] and let k∈ {1,2,3,4} − {i, g(u1), g(u2)}.G[{w1, w2, u1, u2, vk}] is isomorphic to K5, a contradiction. Thus K2* G[Y] and G[Y]∈R(K3, K2;|Y|). Therefore |(N(w1)−N(w2)−N(w3)) ∩V(Hi)|=|Y| ≤ r(K3, K2)−1 = 2. Lemma 2.5 If G[Ai]contains two adjacent vertices w1and w2then |V(Hi)∩N(w1)∩ N(w2)| ≤ 3. Proof. Let Y=V(Hi)∩N(w1)∩N(w2). If K2⊆G[Y] then let u1and u2be the vertices of an edge of G[Y]. G[{w1, w2, u1, u2}] is a subgraph of Gisomorphic to K4and different from K, contradicting Corollary 2.3. Thus K2*G[Y]. By Corollary 2.6, K4*G[Y]⊆Hi. Thus G[Y]∈R(K2, K4;|Y|) and |V(Hi)∩N(w1)∩ N(w2)|=|Y| ≤ r(K2, K4)−1 = 3. Lemma 2.6 Let u∈Ai, then the following statements are verified: dG[Ai](u)≤3, P4 k=1,k6=iek(u)≤8and d(u)≤11. Proof. Suppose, to the contrary, that dG[Ai](u)≥4. Let u1,u2,u3and u4be four different vertices belonging to NG[Ai](u). If K2⊆G[{u1, u2, u3, u4}], then let up, uq∈ {u1, u2, u3, u4}be two adjacent vertices. G[{up, uq, u, vi}] is a subgraph of Gisomorphic to K4different from K, contradicting Corollary 2.3. Thus K2*G[{u1, u2, u3, u4}] and G[{u1, u2, u3, u4}]⊆Hiis isomorphic to K4, contradicting Corollary 2.6. Hence dG[Ai](u)≤3. By Corollary 2.4, K3*G[V(Hi)∩N(u)] ⊆G[N(u)] and, by Corollary 2.6, K4* G[V(Hi)∩N(u)] ⊆Hi. Therefore G[V(Hi)∩N(u)] ∈R(K3, K4;|V(Hi)∩N(u)|) and 8 = r(K3, K4)−1≥ |V(Hi)∩N(u)|=P4 k=1,k6=i|V(Ak)∩N(u)|=P4 k=1,k6=iek(u), completing the second part of the proof. Finally, by Lemma 2.1, d(u)−9≤ej(u), thus 3d(u)−27 ≤P4 k=1,k6=iek(u)≤8 and d(u)≤11. Lemma 2.7 Let u∈Ai, then |Ai| ≤ 2d(u) + dG[Ai](u)−17. 4 Proof. By Lemma 2.1, ej(u)≤d(u)−13 + |Aj|. Therefore d(u)−dG[Ai](u)−1 = P4 k=1,k6=iek(u)≤3d(u)−39 + P4 k=1,k6=i|Ak|= 3d(u)−39 + (21 − |Ai|) and |Ai| ≤ 2d(u) + dG[Ai](u)−17. Corollary 2.7 Let u∈Ai, then dG[Ai](u)≥1and if dG[Ai](u) = 1 then |Ai|= 4. Proof. By Lemma 2.6, d(u) = 1+P4 k=1,k6=iek(u)+dG[Ai](u)≤9+dG[Ai](u). If dG[Ai](u) = 0 then d(u)≤9 and, by Lemma 2.7, |Ai| ≤ 1, contradicting |Ai| ≥ 4. If dG[Ai](u) = 1 then d(u)≤10 and, by Lemma 2.7, |Ai| ≤ 4, thus |Ai|= 4. Corollary 2.8 If |Ai|= 7 and u∈Aithen d(u) = 11. Proof. By Lemmas 2.6 and 2.7, 7 = |Ai| ≤ 2d(u) + dG[Ai](u)−17 ≤2d(u) + 3 −17, thus 2d(u)≥21 and d(u)≥11. Since d(u)≤11, we conclude the proof. In the rest of the paper if we assign the name Wto an ordered set of vertices, {u1, . . . , up} ⊆ Ai, with p≥3, then |(N(uk)−Sp t=1,t6=kN(ut))∩V(Hi)|will be denoted by ak,|(N(uh)∩N(uk)−Sp t=1,t6=h,k N(ut)) ∩V(Hi)|by bh,k, and |(N(uh)∩N(uk)∩N(ul)− Sp t=1,t6=h,k,l N(ut)) ∩V(Hi)|by ch,k,l. Lemma 2.8 If G[Ai]contains a clique of order 3, with vertices u1,u2and u3, then 39 −2|Ai| ≤ d(u1) + d(u2) + d(u3)−dG[Ai](u1)−dG[Ai](u2)−dG[Ai](u3). Proof. Let W={u1, u2, u3}, let w∈V(Hi), and let k∈ {1,2,3,4} − {i, g(w)}. Since G[{u1, u2, u3, w, vk}] is not isomorphic to K5,wis adjacent to at least a vertex of Wand, therefore, every vertex of V(Hi) is adjacent to at least a vertex of W. Hence: a1+a2+a3+b1,2+b1,3+b2,3+c1,2,3=|V(Hi)|= 21 − |Ai|(1) On the one hand, since u1is adjacent to d(u1)−dG[Ai](u1)−1 vertices of Hiwe have: a1+b1,2+b1,3+c1,2,3=d(u1)−dG[Ai](u1)−1 (2) Analogously, u2and u3are adjacent to d(u2)−dG[Ai](u2)−1 and d(u3)−dG[Ai](u3)−1 vertices of Hirespectively, thus: a2+b1,2+b2,3+c1,2,3=d(u2)−dG[Ai](u2)−1 (3) a3+b1,3+b2,3+c1,2,3=d(u3)−dG[Ai](u3)−1 (4) On the other hand, by Lemma 2.4: a1=|(N(u1)−N(u2)−N(u3)) ∩V(Hi)| ≤ 2 (5) a2=|(N(u2)−N(u1)−N(u3)) ∩V(Hi)| ≤ 2 (6) 5 a3=|(N(u3)−N(u1)−N(u2)) ∩V(Hi)| ≤ 2 (7) Finally, from (2) + (3) + (4) + (5) + (6) + (7) −2(1) we have: c1,2,3≤d(u1) + d(u2) + d(u3)−dG[Ai](u1)−dG[Ai](u2)−dG[Ai](u3)−39 + 2|Ai|. We obtain the result noting that c1,2,3is non-negative. Corollary 2.9 If G[Ai]contains a clique of order 3, then |Ai| ≥ 6and if |Ai|= 6 then for any vertex uof the clique, dG[Ai](u) = 2 and d(u) = 11. Proof. Let u1,u2, and u3be the three vertices of the clique. By Corollary 2.7, dG[Ai](u1), dG[Ai](u2), dG[Ai](u3)≥1 and, by Lemma 2.6, d(u1), d(u2), d(u3)≤11. Therefore, by Lemma 2.8, 39−2|Ai| ≤ d(u1)+d(u2)+ d(u3)−dG[Ai](u1)−dG[Ai](u2)− dG[Ai](u3)≤11 + 11 + 11 −1−1−1 = 30 and |Ai| ≥ 5. Hence, by Corollary 2.7, dG[Ai](u1), dG[Ai](u2), dG[Ai](u3)≥2, and 39 −2|Ai| ≤ d(u1) + d(u2) + d(u3)−dG[Ai](u1)− dG[Ai](u2)−dG[Ai](u3)≤11 + 11 + 11 −2−2−2 = 27, thus |Ai| ≥ 6. If |Ai|= 6, on the one hand, 27 = 39 −2|Ai| ≤ d(u1) + d(u2) + d(u3)−dG[Ai](u1)− dG[Ai](u2)−dG[Ai](u3)≤d(u) + 11 + 11 −2−2−2 = d(u) + 16, hence d(u) = 11. On the other hand, 27 = 39−2|Ai| ≤ d(u1)+d(u2)+d(u3)−dG[Ai](u1)−dG[Ai](u2)−dG[Ai](u3)≤ 11 + 11 + 11 −dG[Ai](u)−2−2 = 29 −dG[Ai](u), therefore dG[Ai](u) = 2. Corollary 2.10 Let u∈Ai, then d(u)≥10. Proof. By Lemma 2.6, dG[Ai](u)≤3. If d(u)≤9 then by Lemma 2.2, d(u) = 9 and, by Lemma 2.7, |Ai| ≤ 2d(u) + dG[Ai](u)−17 ≤18 + 3 −17 = 4, thus |Ai|= 4. By Lemma 2.1, 8 −dG[Ai](u) = d(u)−1−dG[Ai](u) = P4 k=1,k6=iek(u)≤P4 k=1,k6=i(|Ak| − 13 + d(u)) = P4 k=1,k6=i|Ak|−12 = (21 −4)−12 = 5. Hence dG[Ai](u)≥3 and uis adjacent to the three vertices of Ai− {u}. By Corollary 2.9, K3*G[Ai] and at least two of the three vertices of Ai− {u}are adjacent. Let w1and w2denote them. Then u,w1and w2are the vertices of a clique of G[Ai], contradicting Corollary 2.5 and completing the proof. From Corollaries 2.5 and 2.9 and Lemma 2.6, it is easy to check the next result: Corollary 2.11 1. If |Ai|= 4 then G[Ai]is isomorphic to 2K2,P4or C4. 2. If |Ai|= 5 then G[Ai]is isomorphic to C5. 3. If |Ai|= 6 then G[Ai]is isomorphic to C6or SK2,3(the graph obtained subdividing one edge of K2,3). Now, we prove that G[Ai] is isomorphic neither to C5nor to SK2,3. Lemma 2.9 G[Ai]is not isomorphic to C5. the electronic journal of combinatorics 18 (2011), #P90 6 Proof. Suppose, to the contrary, that G[Ai] is isomorphic to C5. Let W={u1, . . . , u5} denote its vertices, with its edges being u1u2,u2u3,u3u4,u4u5and u1u5. Let w∈V(Hi). By Lemmas 2.1 and 2.6 and Corollary 2.10, 1 ≤d(w)−9≤ei(w)≤ d(w)−13 + |Ai|=d(w)−8≤3, thus every vertex of Hiis adjacent to 1, 2 or 3 vertices of G[Ai] and we have: 5 X k=1 ak+X 1≤k<m≤5 bk,m +X 1≤k<m<n≤5 ck,m,n =|V(Hi)|= 16 (8) On the one hand, by Lemma 2.5: b1,2+c1,2,3+c1,2,4+c1,2,5=|V(Hi)∩N(u1)∩N(u2)| ≤ 3 (9) b2,3+c1,2,3+c2,3,4+c2,3,5=|V(Hi)∩N(u2)∩N(u3)| ≤ 3 (10) b3,4+c1,3,4+c2,3,4+c3,4,5=|V(Hi)∩N(u3)∩N(u4)| ≤ 3 (11) b4,5+c1,4,5+c2,4,5+c3,4,5=|V(Hi)∩N(u4)∩N(u5)| ≤ 3 (12) b1,5+c1,2,5+c1,3,5+c1,4,5=|V(Hi)∩N(u1)∩N(u5)| ≤ 3 (13) On the other hand, let Y=V(Hi)−N(u1)−N(u3). By Corollary 2.6, K4*G[Y]⊆ Hi. If K2⊆G[Y] then let w1and w2be the vertices of an edge of G[Y] and let k∈ {1,2,3,4}− {i, g(w1), g(w2)}.G[{u1, u3, w1, w2, vk}] is isomorphic to K5, a contradiction. Thus K2*G[Y], G[Y]∈R(K4, K2;|Y|) and: a2+a4+a5+b2,4+b2,5+b4,5+c2,4,5=|V(Hi)−N(u1)−N(u3)|= =|Y| ≤ r(K4, K2)−1 = 3 (14) Similarly G[V(Hi)−N(u1)−N(u4)] ∈R(K4, K2;|V(Hi)−N(u1)−N(u4)|) and: a2+a3+a5+b2,3+b2,5+b3,5+c2,3,5≤3 (15) G[V(Hi)−N(u2)−N(u4)] ∈R(K4, K2;|V(Hi)−N(u2)−N(u4)|) and: a1+a3+a5+b1,3+b1,5+b3,5+c1,3,5≤3 (16) G[V(Hi)−N(u2)−N(u5)] ∈R(K4, K2;|V(Hi)−N(u2)−N(u5)|) and: a1+a3+a4+b1,3+b1,4+b3,4+c1,3,4≤3 (17) 7 G[V(Hi)−N(u3)−N(u5)] ∈R(K4, K2;|V(Hi)−N(u3)−N(u5)|) and: a1+a2+a4+b1,2+b1,4+b2,4+c1,2,4≤3 (18) From (9) + ···+ (18) we have: 3 5 X k=1 ak+ 2X 1≤k<m≤5 bk,m + 2X 1≤k<m<n≤5 ck,m,n ≤30 (19) Finally, from (19) −2(8) we obtain P5 k=1 ak≤ −2. This contradiction completes the proof. Lemma 2.10 G[Ai]is not isomorphic to SK2,3. Proof. Suppose, to the contrary, that G[Ai] is isomorphic to SK2,3. Let W={u1, . . . , u4} be the set of vertices of Aiof degree 2 in G[Ai], with its only edge being u1u2. Every vertex of Wbelongs to a clique of order 3 contained in G[Ai], thus, by Corollary 2.9, each vertex of Whas degree 11 in G. Let h=|V(Hi)∩T4 n=1 N(un)|. Since d(u1) = 11 and dG[Ai](u1) = 2 we have that, |N(u)∩V(Hi)|, the number of edges incident to u1and a vertex of Hiis: a1+b1,2+b1,3+b1,4+c1,2,3+c1,2,4+c1,3,4+h=d(u1)−dG[Ai](u1)−1 = 8 (20) On the one hand, by Lemma 2.4: a1+b1,2=|(N(u1)−N(u3)−N(u4)) ∩V(Hi)| ≤ 2 (21) On the other hand, let Y=V(Hi)∩N(u1)∩N(u3). By Corollary 2.4, K3*G[Y]⊆ G[N(u1)]. If K2⊆G[Y] then let w1and w2be the vertices of an edge of G[Y] and let k∈ {1,2,3,4}− {i, g(w1), g(w2)}.G[{u1, u3, w1, w2, vk}] is isomorphic to K5, a contradiction. Therefore K2*G[Y], G[Y]∈R(K3, K2;|Y|) and: b1,3+c1,2,3+c1,3,4+h=|V(Hi)∩N(u1)∩N(u3)|=|Y| ≤ r(K3, K2)−1 = 2 (22) Similarly G[V(Hi)∩N(u1)∩N(u4)] ∈R(K3, K2;|V(Hi)∩N(u1)∩N(u4)|) and: b1,4+c1,2,4+c1,3,4+h≤2 (23) From (21) + (22) + (23) −(20) we obtain c1,3,4+h≤ −2, a contradiction. Finally, we prove Theorem 2.1: Proof. By Corollaries 2.8 and 2.11 and Lemmas 2.9 and 2.10, |A1|= 7, |A2|= 6, |A3|= |A4|= 4, G[A2] is isomorphic to C6and all vertices of A1∪A2have degree 11 in G. Let sdenote the number of edges of G[A3]. 8 By Corollary 2.6, H4∈R(K4, K4; 17). Kalbfleisch [14] proved that there is exactly one graph in the set R(K4, K4; 17) and every vertex of this graph has degree 8, thus, for any w∈V(H4), dH4(w) = 8. If u∈A1∪A2, by Lemma 2.1, 2 = d(u)−9≤e3(u)≤d(u)−13 + |A3|= 2, thus e3(u) = 2 and the number of edges of H4with a vertex belonging to A1∪A2and another vertex belonging to A3is Pw∈A3(e1(w) + e2(w)) = Pu∈A1∪A2e3(u) = 2|A1∪A2|= 26. If w∈A3, then 8 = dH4(w) = dG[A3](w) + e1(w) + e2(w). Thus 32 = Pw∈A38 = Pw∈A3dG[A3](w) + Pw∈A3(e1(w) + e2(w)) = 2s+ 26 and s= 3. Hence, by Corollary 2.11, G[A3] is isomorphic to P4. In the following, we assume that i= 3. Let W={u1,...,u4}be the vertices of A3, with the edges of G[A3] being u1u2,u2u3and u3u4. Let w∈V(H3). By Lemmas 2.1 and 2.6 and Corollary 2.10, 1 ≤d(w)−9≤e3(w)≤ d(w)−13 + |A3|=d(w)−9≤2, thus every vertex of H3is adjacent to 1 or 2 vertices of A3and |N(u2)∩V(H3)|is: a2+b1,2+b2,3+b2,4=d(u2)−dG[A3](u2)−1≥10 −2−1 = 7 (24) Let Y1=V(H3)∩N(u2)−N(u1)−N(u3). By Corollary 2.4, K3*G[Y1]⊆G[N(u2)]. If K2⊆G[Y1] then let w1and w2be the vertices of an edge of G[Y1] and let k∈ {1,2,4} − {g(w1), g(w2)}.G[{u1, u3, w1, w2, vk}] is isomorphic to K5, a contradiction. Hence K2*G[Y1], G[Y1]∈R(K3, K2;|Y1|) and: a2+b2,4=|V(H3)∩N(u2)−N(u1)−N(u3)|=|Y1| ≤ r(K3, K2)−1 = 2 (25) On the one hand, by Lemma 2.5: b1,2=|V(H3)∩N(u1)∩N(u2)| ≤ 3 (26) On the other hand, let Y2=V(H3)∩N(u2)∩N(u3). If K2⊆G[Y2] then let w1and w2 be the vertices of an edge of G[Y2]. G[{w1, w2, u2, u3}] is a subgraph of Gisomorphic to K4 and different from K, contradicting Corollary 2.3, thus K2*G[Y2]. If K2⊆G[Y2] then let w1and w2be the vertices of an edge of G[Y2] and let k∈ {1,2,4} − {g(w1), g(w2)}. G[{u1, u4, w1, w2, vk3}] is isomorphic to K5, a contradiction. Hence K2*G[Y2], G[Y2]∈ R(K2, K2;|Y2|) and: b2,3=|V(H3)∩N(u2)∩N(u3)|=|Y2| ≤ r(K2, K2)−1 = 1 (27) From (25)+(26)+(27) we obtain a2+b1,2+b2,3+b2,4≤6, contradicting (24) and completing the proof of Theorem 2.1. 9