Partitioning a Graph into Two Square-Cycles Genghua Fan H. A. Kierstead" DEPARTMENT 0F MATHEMATICS ARIZONA STATE UNIVERSITY TEMPE, AZ 85287 e-mai1:fanQmath./a.asu.edu e-mail:kierstead@math.la.asu.edu ABSTRACT A square-cycle is the graph obtained from a cycle by joining every pair of vertices of distance two in the cycle. The length of a square-cycle is the number of vertices in it. Let G be a graph on n vertices with minimum degree a t least $n and let c be the maximum length of a square-cycle in G. Posa and Seymour conjectured that c = n. In this paper, it is proved that either c = n or 5 c 5 $n. As an application of this result, it is shown that G has two vertex-disjoint square-cycles C1 and Cz such that V ( G )= V ( c 1 )U V ( c 2 ) .0 1996 John Wiley & Sons, Inc. in 1. INTRODUCTION All graphs considered are simple and undirected. S(G) denotes the minimum degree of a graph G. Let P be a path (cycle). The kth power of P is the graph obtained from P by joining every pair of vertices with distance at most k in P. An edge is called a k-chord of P if it joins two vertices of distance k in P. We call the 2nd power of P a square-path (-cycle). (For technical reasons, the empty set is regarded as a square-cycle.) A hamilronian square-path (-cycle) is a square-path (-cycle) that contains all the vertices of the graph. A classical theorem of Dirac [l] states that if G is a graph on n vertices with 6(G) 2 :, then G contains a hamiltonian cycle. In 1963 Posa (see Erdos [2]) conjectured that if S(G) 2 $n,then G contains a hamiltonian square-cycle. In 1973 Seymour [6] introduced * Research partially supported by Office of Naval Research Grant N00014-90-J-1206. Journal of Graph Theory Vol. 23, No. 3, 241-256 (1996) 0 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/030241-16 242 JOURNAL OF GRAPH THEORY the more general conjecture that if S(G) 2 [ k / ( k +l ) ] n then , G contains the kth power of a hamiltonian cycle. As Seymour pointed out, if his conjecture is true, the proof is likely to be very hard, because it implies the remarkably difficult theorem of Hajnal and Szemeredi [6] that any graph G with maximum degree A can be properly colored with A + 1 colors so that no two color classes differ in size by more than one. There has been progress on Posa’s conjecture. Fan and Haggkvist [3] proved that if S(G) 2 :n, then G contains a hamiltonian square-cycle. Fan and Kierstead [4] showed that for every E > 0, there exists m such that if n > m and S(G) > [(2 ~ ) / 3 ] nthen , G contains a hamiltonian squarecycle. They [5] also proved that if 6(G) 2 [(2n- 1)/3], then G contains a hamiltonian square-path. If H is a subgraph of G , G - H denotes the subgraph obtained by deleting all the , H(z) vertices of H together with all the edges with at least one end in H . For z E V ( G ) N is the set, and d ( z , H ) the number, of vertices in H that are joined to z. We denote ) N H ( z )n N H ( ~ )(In . the case by zy the edge with ends z and y and define N ~ ( z y = that H = G, we simply use N(x),d(z),and N(zy).) If F is another subgraph of G, we define d ( F , H ) = C v E I / ( F ) d ( ~ , H By) . the definition, d ( F , H ) = d ( H , F ) , and if V ( F )n V ( H ) = 0, then d ( F ,H ) is simply the number of edges with one end in F and the other end in H . The complete graph on m vertices is denoted by K,,,. The third power of a path is also called a cube-path. If P = z1z2. . . z pis a square-path (cube-path), we say that P starts at 21x2. By definition, the existence of a square-path starting at z1z2does not imply the existence of a square-path starting at z2z1.Here the order of the endpoints of edges is significant. This is the only case where we distinguish xy from yx for the same edge. In such a case, for clarity, we shall use the term ordered edge instead of edge. If P = zyQzw is a square-path (so Q is a square-path itself), we say that xy is connected to zw through Q, or by P. A square-cycle is optimal if (i) it is a longest square-cycle; (ii) subject to (i), it has the maximum number of 3-chords; (iii) subject to (i) and (ii), it has the maximum number of 4-chords. A square-cycle C is chord-maximum if it is optimal and, subject to this, the subgraph induced by V ( C ) has maximum number of edges among all optimal square+~, cycles. Let C = u1u2 . . . uCul be a square-cycle, where c = IV(C)I and u , ~ ,u,u,+2 are 1- and 2-chords of C respectively, 1 5 i 5 c. (Addition of indices is taken modulo c.) By i < 1, we mean that u,, u,+1,. . . , IL] are around C in the order consistent with a fixed orientation of C. Let G be a graph on n vertices with S(G) 2 Section 2 is devoted to general lemmas that are needed in other sections. In Section 3, we prove that if G has no hamiltonian square-cycle, then any square-cycle in G has length at most In Section 4, it is showed that the longest square-cycle in G has length at least n/2. Finally, by using the two results, we establish in Section 5 that the vertices of G can be partitioned into at most two squarecycles. + in. in. 2. LEMMAS Lemma 2.1 (4, Lemma 3.21. Let C = u1u2. . . utl,.ulbe an optimal square-cycle in a graph G. Let x be a vertex in G - C. (a) d ( z , Q) 5 $ q + 1 for any segment Q = u1u2. . . uq--luqof C, with equality only if d ( z , U I U 2 ) = d ( z ,uq--luq)= 2. PARTITIONING INTO TWO SQUARE CYCLES 243 (b) d(x,C ) 5 (2c + 1)/3, with equality only if, by relabeling, Nc(x)= v(c)\ { u g k : 1 5 k 5 ( c - 1)/3}. d ( x , u C u 1 u 2=) 3 and Remark. The second part of Lemma 2.l(a) is not contained in [4], but it follows immediately by applying the first part to the segments Q - a1a2 and Q - a q - l a q . in, Lemma 2.2. Let G be a graph on n vertices with 6(G) 2 where n 2 7. Suppose that S is an independent set of G with ( S / 2 f and xy E E(G) with x E S. Then G has a hamiltonian square-cycle C such that xy is neither a 1-chord nor a 2-chord of C. Proof. Since S is an independent set, we have that S(G) 5 n - I S1 and so I S 15 n - S(G) 5 2 , which implies that (SI= n/3, S(G) = $n, and each vertex of S is joined to every vertex of G - S. Let S = { 2 1 , 5 2 , . . . , x k } , where x1 = x and Ic = IS\. Since S(G - S ) 2 S(G)- I S1 = n / 3 = i ( V ( G- S)l,it follows from a classical theorem of Dirac [ l ] that G - S has a hamiltonian cycle, say a1u2 . . . uv,ul, where m = IV(G - S ) ( = 2k and a,, = y. Noting that m 2 5 (since n 2 7) and each 2, is joined to every vertex of G - S, we see that ala2x1a3a4x2a5a6x3... a23-1a2,xJa23+1a23+2...anL-1a,,xkalu2 is a hamiltonian square-cycle in G with the required property. I Lemma 2.3. Let C = u1u2. . . ucul be a chord-maximum square-cycle in a graph G. Let W 2 V ( G - C ) with d(v,C) = (2c + 1)/3 for all v E W. (a) If c = 4, then W is an independent set in G; (b) If c # 5 and W # 0, then there is a set S C V ( C )with / S /= ( c - 1)/3 such that W U S is an independent set in G and N c ( a ) = Nc(6) for every a , 6 E W U S. Proof. (a) If the statement is not true, let 2,y E W with xy E E(G).Since d ( v ,C) = 3 for all v E W, we have that 2 5 INc(xy)( 5 3. If i N ~ ( x y ) = ( 3, we have a K5; if INc(xy)l = 2, we have a square-cycle C' with V ( C ' )= V ( C )U {x,y}. In either case, we have a contradiction to the maximality of c. This proves (a). (b) Since W # 0, c = 1 (mod 3), and since c 2 5, we have that c 2 7. Let x E W. By Lemma 2.l(b), with a proper labeling we have that Nc(x)= V ( C )\ S, where S = { u 3 k : 1 5 k 5 ( c - 1)/3}. Let C, be the square-cycle obtained from C by replacing u3, with x, that is, C, = u1u2 ..'u3t-2u3t-1xu3t+iu3t+2...u,.ul, where 1 5 t 5 ( c - l)/3. First, we have that U3?& $! E ( G ) since, otherwise, &u1xu2u4u3u5ug . . . u, would be a square-cycle of length c + 1. And analogously ~ , - 1 ~ , - 4 $! E ( G ) . Now, since u,x is a 3-chord in C1 and by the optimality of C, we have that ucu3E E ( G ) ,and analogously, u,-1u2 E E ( G ) . (2.1) Next, we have that uc-lu3 q! E ( G ) since, otherwise, uc-1ucu3ulu22u4u5.~. u , - ~ would be a square-cycle of length c I. Moreover, since xu7 is a 4-chord in C1,it follows from E 4E ( G ) follows from the optimality the optimality of C that ~ 3 1 1 7E E ( G ) .Then u 3 t ~ 3 t + ~ 4-chords in C,, 2 5 t 5 ( c - 4)/3. of C and from the fact that xugt--q and Z U ~ , +are We have seen that u 3 U 6 q! E(G). If ~ 3 E E (~G ) for ~some t ,32 5 t ~5 ( c -~4)/3, then u , 2 ~ ~ 2 u ~ ( u ~ u g u g (u3t+lu3tu3t+2)uL3t+3U3tf4 ) ( ~ ~ u ~ u ~ ) ~ ~ ~ . . . U , - ~ U , is a square-cycle of length c + 1. Therefore we have that + $! E ( G ) u3tu3t+3 c-4 3 for all t , 1 5 t 5 -. ~ 244 JOURNAL OF GRAPH THEORY We note that C,, 1 5 t 5 (c - 1)/3, has the same length as C, and by (2.2), has as many 3-chords as C does. Since C is chord-maximum, d(u3,, C) 2 d ( z , C), and since Ct is also optimal, we have that d ( u S t ,C) = d ( z , C) = (2c + 1)/3. We claim that Nc(wgt,)= Nc.(z). If this is not true, then u g t is joined to some u 3 k E S. We may suppose that k > t and choose k - t to be as small as possible. By (2.2), k 2 t + 2, and by the minimality ~ ~ the ) property of k - tlu3tusk-:3 $! E ( G ) . Since d(u3t,Ct)= (2c + 1 ) / 3 , N ~ , ( uhas described in Lemma 2.l(b). Noting that u3tu3/c E E ( G ) and u S t u 3 k u 3 @ E ( G ) ,we see that d ( u S t ,u 3 k - - 2 u ~ k - - 1 ~ 3 k=) 3. It follows from (2.1) (with Ct, uSt in the position of C, z) that u:jk--3u:$k- E E ( G ) ,contradicting (2.2). Therefore, NC(uSt)= Nc(x) for all ulgtE S, which implies that S U { z } is an independent set. Next we show that Nc(y) = N c ( z ) for all y E W \ {z}. By Lemma 2.l(b), d ( y , ~ , u , + ~ , u , + ~= ) 3 for some u., E V ( C )and N(y) = V ( C )\ S’, where S’ = {u,+:$~ : i 2 l} and /S‘I = (c - 1)/3. If j = c, then Nc(y) = N c ( z ) . Suppose that this is not the case. For 1 5 t 5 (c - 4)/3, if j = 3t or 3t + 1, then, as seen in (2.1), uju3+3E E ( G ) , contradicting (2.2). Thus, j E {c - 2, c - 1,1,2}u {3t + 2 : 1 5 t 5 ( c - 4)/3}. It is easily verified that for any such value of j, S’ n S = 0. So S U {x} and S’ u {y} are two independent sets, and moreover, S C Nc(y) and S’ C Nc(x).Let D be the graph induced by V(C)U{z,y),p lu s th eed g ex y if itis n o tin E (G ). S o d ( w , D ) = (2c+1)/3+1 = $lV(D)l for all v E S u S ’ u { z , y } . Note that ( S U { Z } / = IS’u{y}/ = ( c + 2 ) / 3 = i l V ( D ) l .We see that d ( v , D ) 2 (SU{z}(+(S’U{y}(= $lV(D)I for all v E V ( D ) \ ( S U S ’ u { z , y } ) . Therefore, 6 ( D ) > { l V ( D ) ( .Note that IV(D)l 2 c + 2 > 9. It follows from Lemma 2.2 that D has a hamiltonian square-cycle that does not contain the edge zy,and so it is a hamiltonian square-cycle of length c + 2 in G. This contradiction shows that Nc(y) = N<:(x) for all YE W\{xI. Finally we need to show that W is an independent set. If this is not true, let x , y E W and zy E E ( G ) . Since N c ( z ) = Nc(y) and c 2 7, we may replace a vertex of S by the edge zy and obtain a square-cycle of length c + 1. Thus W is an independent set and the proof is completed. I Lemma 2.4. Let G be a graph on n vertices with S(G) 2 $ n and let C = u1u2 ”.u,:u1 be an optimal square-cycle in G. Then either c = n or c 2 5. Prooj For n 5 9, the result can be easily verified. We assume that n 2 10. If c = 3, then G contains no K4. This means that N ( u v ) is an independent set for any edge uv E E ( G ) . Since S(G) 2 $ n , we have that ( N ( u v ) l2 n/3, and the by Lemma 2.2, c = n. If c = 4, then d(v,C) 6 3 for all v E V ( G - C), and by Lemma 2.3(a), S = {z E V ( G- C ) : d(x,C) = 3) is an independent set. Moreover, 8 -n 5 d ( C , G) 6 2(n - c ) 3 + IS1 + 12 = 2n + 4 + IS/, which implies, since n 2 10, that /St> - 1. Let z E S. Since S is an independent set and d ( z , C )5 c - 1, we see that d(x) 5 n - 1 - IS/, and thus I S1 5 n - 1 - d(x) 1. - 1, a contradiction. This proves the lemma. I Lemma 2.5. Let C = u1u2. . . u,ul be a chord-maximum square-cycle in a graph G. Let xy be an edge in G - C. PARTITIONING INTO TWO SQUARE CYCLES 245 (b) If d(xy,C) = i c and c # 3, then d ( ~ y , u ~ u , +I~3) for all consecutive U ~ , U , + E~ V ( C )and there are s , t such that x E N ( U , ~ U , ~E+N~()U, ~~ U ~ and + ~ s) , 2 5 t 5 s + 4. + Proof. (a) If c = 1 (mod 3), by Lemma 2.l(b) and Lemma 2.3, d(zy, C) 5 (4c - 1)/3; if c 1 (mod 31, by Lemma 2.l(b), d(zy, C) 5 4c/3. (b) By the given conditions, c = 0 (mod 3) and c 2 6, and it follows from Lemma 2.l(b) that d ( x , C ) = d ( y , C ) = $c. Let Q be any segment of C with IV(Q)I = 3k + 2. Then, for any a E (5, y}, by Lemma 2.l(a) d ( a ,C - Q) 5 $(c - IV(Q)\)+ 1. Noting that c - IV(Q)I = 1 (mod 3), we have d ( a , C - Q) 5 $ ( c - IV(Q)I)+ $, and therefore + 2 3 d(a, Q) = -C - 2 1 d(a,C - Q ) 2 -IV(Q)I - - = 2k 3 3 + 1. (2.3) Suppose, to the contrary, that d(xy, U , U , + ~ ) = 4 for some i. By relabeling, we may assume that d(xy, u1u2)= 4. By the maximality of c, either d(u,, xy) = 0 or d ( u 3 ,xy) = 0. Without loss of generality, we assume that d(u3,zy) = 0. By (2.3) with Q = u 3 u 4 , d ( u 4 , z y = ) 2. Then d ( u 5 , x y ) = 0 for otherwise a longer square-cycle results by replacing by xy. Again by (2.3) with Q = u5u6,d(u6,xy) = 2. We claim that c 2 9. If this is not true, then c = 6 and {a1,u2, u4,u6,x,y} induces either K6 or K6 minus the edge ~ 4 ~ which 1 , gives a square-cycle with at most one 3-chord missing. Thus, since it is optimal, C contains all the 3-chords, except for at most one. Then the graph induced by V ( C )U {z,y} has a square-cycle of length at least 7, a contradiction. Therefore c 2 9, as claimed. If d(u,,xy) = 0, by (2.3) with k = 2 and Q = u,-2uc-1u[~u1u2u3u4u5,we obtain that d(u,-2u,-l, xy) = 4 and ~,-2u,-~zyu~u2 . . . tLc-3uc-2 is a square-cycle of length c + 1. Thus we assume that d(u,, zy) 2 1. By symmetry, we may assume that ucxE E ( G ) . Note that d(u3, zy) = d ( u 5 ,zy) = 0. By (2.3) with Q = u3u4u5u6u7,we have that d(u6u7,zy) = 4. Thus C' = u,ulu2zu4yu62L7"'uc-1u[: is a square-cycle of length c. We note that zu,.,xu6,yu2 are 3-chords in C'. By the choice of C, there must be at least three 3chords incident with u3 and u5. So either u,u3 or u5u8 is a 3-chord in C. In the former case, u,u1u3th2u4xy'zL6u7.. . u,-~u,, and in the latter case ulu22yuqu6ugu7ug... u,ul, is ) 3 for all a square-cycle of length c 1. This contradiction shows that d(zy, U , U ~ + ~ 5 u , + ~E V ( G ) . consecutive ui, Since d ( z , C ) = i c , we may assume that 17: E N(u1u2).By the above result, y q! N ( u l u Z ) Without . loss of generality, we suppose that yu2 # E ( G ) . By (2.3) with Q = u2u3u4ugu6, we have that y E N ( ~ ~ u j + ~5) j, 3 5 5. This completes the proof of Lemma 2.5. I + Lemma 2.6. Let C = u 1 u ~. . . u,ul be a chord-maximum square-cycle in a graph G. Let T be a triangle in G - C. Then d ( T , C) 5 2c - 1. Pruuj If c = 3, then d(v,C) I 2 for all 'u E V ( T ) ,which gives that d ( T , C) I 6. But, if d ( T ,C) = 6, then, since G has no K4, the subgraph induced by V ( T )u V ( C )is a square-cycle of length 6, contradicting the maximality of c . Thus d(T,C) 5 5 = 2c - 1. We assume therefore that c 2 4. Let x,y, z be the three vertices of T . If the assertion is not true, then by Lemma 2.5, 2 3 d(x,C ) = d ( y , C ) = d ( z ,C ) = -c. (2.4) 246 JOURNAL OF GRAPH THEORY and d(T,uiu,+l) 5 4 for all consecutive u i ,ui+l E V ( C ) .By (2.41, d(T,C) = 2c, and it follows that d(T,U , U , + ~ ) = 4 for all consecutive ui, u , + ~E V ( C ) .We note that c E 0 (mod 3 ) by (2.4), and hence c 2 6. Case 1. There is some s such that d(u,, T ) = 1, say d(ul, T ) = 1. Then d ( u 2 ,T ) = 3, which implies that d(u3,T ) = 1, and then d(u4,T ) = 3 , . . . , d ( u ~ k + lC, ) = 1,d ( ~G)~= ~ , 3 , . . . . We may suppose that u1x E E ( G ) .If c = 6, then u6U1tL2xyzu4u6 is a square-cycle of length 7, a contradiction, thus c 2 9. If u1 and us are joined to distinct vertices of T , then replacing u3 by T gives a square-cycle of length c 2 . Thus ul and u5 are joined to the same vertex x. By the same reason, u3 and u7 are joined to the same vertex in T . Since x cannot be joined to the four consecutive vertices, the vertex in T joined to u7 must be distinct from x, say it is y. Then u1U.m4zyu6u7 . . . u,.u1 is a square-cycle of length c + 1, thus case 1 leads to a contradiction. Case 2. d ( u i , T )= 2 for all u, E V ( C ) .By (2.4) and Lemma 2.5(b), we may assume that d ( u l ,zy) = 2 and d ( u 2 ,yz) = 2 . Case 2a. u,y E E ( G ) .Noting that y, by the maximality of c, cannot be joined to four consecutive vertices, we have that u 3 y @ E ( G ) and so d ( u g ,xz) = 2 . If u,x E E ( G ) ,then uu,:u1xyzu2u~~ is~a" usquare-cycle c of length c 3. Thus we assume that ucz E E ( G ) . If ulz E E ( G ) , then u,u1yu2zu3u4. "u, is a square-cycle of length c + 2; otherwise d(u~q, xy) = 2 , then ulu2yzZu3u4 . . . ucul is a square-cycle of length c + 3. Case 2b. u,y @ E ( G ) and so d ( u , , x z ) = 2 . Clearly, u3z @ E ( G ) for otherwise, as before, u,ulzyzuzu:3. . . u c is a square-cycle of length c + 3 . So d ( u g , x y ) = 2 . Since y cannot be joined to four consecutive vertices, u4y @ E ( G ) and SO d ( u 4 , x z ) = 2 . If U , . - ~ X E E ( G ) ,then ~ ~ - ~ u , x z y u .~ u,.-1 u ~is u a4square-cycle ~~ of length c + 2 ; otherwise d(u,-l,yz) = 2 , then u,-1u,zxyu1u2. . . u , - ~is a square-cycle of length c + 3. In either case we have a contradiction. This completes the proof of Lemma 2.6. I + + Lemma 2.7. Let G be a graph on n vertices and let C be a chord-maximum square-cycle of length c in G. Set H = G - C. If H f 0 and d(v,G) 2 $ n for all w E V ( H ) ,then E ( H ) f 0 and any edge of H is contained in a K4 in H . . Lemma 2.l(b), S ( H ) 2 (2h - 1)/3 > 0 and so E ( H ) # 8. Proof. Let h = / V ( H ) / By For any e E E ( H ) ,by Lemma 2.5(a), d ( e , H ) 2 t h , which implies that e is contained in a triangle, say T , in H . By Lemma 2.6, d ( T , H ) 2 2h 1 and so T is contained in a K4 in H . I + Lemma 2.8. Let G be a graph on n vertices with b(G) 2 $71 and let C be a chordmaximum square-cycle of length c in G, where c < n. Set H = G - C and h = / V ( H ) I . Let Q be a chord-maximum square-cycle of length q in H . If q < h, then q I h - 4. Proof. By Lemma 2.4, c 2 5. If d (v,H ) 2 $ h for all E V ( H - Q ) , then by Lemma 2.7, H - Q contains a K 4 , and we are done. Assume that there is y E V ( H - Q) such that d ( y , H ) < gh, which together with Lemma 2.l(b) implies that d(y, C) = (2c + 1)/3 (so c = 1 (mod 3)). Let H' = H - y. For any w E V ( H ' ) , if d(w,C) = (2c + 1)/3, then by Lemma 2.3, vy @ E ( G ) .This means that b ( H ' ) > i ( h - 1).If q < ( h - l ) , then the result follows by the arguments we just used. Otherwise, q = h - 1 and d ( y , Q) = (2q + 1)/3 (so q = 1 (mod 3)). If q 2 5, by applying Lemma 2.3(b) to y and Q, we have an independent set S1 C V ( Q )suchthat ISl]= (q-1)/3,S1u{y}isanindependentset,andNQ(a) = N Q ( ~ ) , implying d ( a , C) = (2c + 1)/3, for all a E S1. If q = 4, let S1 = { z } , where z is the only vertex in Q not joined to y. (Note that d ( z , C) 2 $ n - 3 = (2c + 1)/3 and hence d ( z , C) = ( 2 c + 1)/3 by Lemma 2.1(b).) In either case, S1U {y} is an independent set with PARTITIONING INTO TWO SQUARE CYCLES 247 IS11 = ( q - l ) / 3 a n d d ( w , C ) = ( 2 c + 1 ) / 3 f o r a l l v ~S 1 u { y j . ItfollowsfromLemma2.3 that there is an independent set S2 C V ( C )such that IS2J = ( c - 1)/3 and S2 U S1U { y j is an independent set, which has cardinality n/3, and by Lemma 2.2, c = n, a contradiction. I This completes the proof. Lemma 2.9. Let G be a graph on n vertices and let P = ~ 1 ~ . .2. uP-1uP ~ 3 be a squarepath starting at u1u2 and ending at uP-luP.Set H = G - P and h = IV(H)I. Let A = {u E V ( H ): d(v,G ) 2 (5n 1)/6}. If p > 2h - 5, then G has a square-path P’ starting at u1u2 and ending at uP-luPwith V(P’) = V ( P )u A. + Proof: We use induction on / A / .If A = 0, there is nothing to prove, and thus we assume that A # 0 and let a E A . We note that d ( a , P ) 2 (5n + 1)/6 - (h - 1) = z3 ( p 1) ( p 5 - 2h)/12 > i ( p + 1), which implies that there are four consecutive vertices u2,uz+l,u,+2,ut+3on P that are all joined to a, so that Q = u1u2 . . . u,uz+lau~,+Zu2+3~,-I~~ is a square-path. Let H’ = H - Q and A’ = A \ { u } . Obviously IV(Q)I > 21V(H’)J - 5, and the result follows by induction. I + + + Lemma 2.10. Let G be a graph on n vertices with a square-path P = u1u2 . . .~ , - 3 ~ , - 2 such that G - P is a single edge, denoted by xy. Suppose that u1 $ N(zy). If d(u1,G) + d(y,G) 2 $n - 1 and d(u1u2,G) + d(xy,G) 2 (10n - 8)/3, then G has a hamiltonian square-path starting at sy and ending at ~ , - 3 ~ , , - 2 . Proof: Let B = {u,u,+~: u,E N(zy) and u,+1 E N ( u I z L1~5) ,i I n - 3). For each E B and i n - 3 (note that u1 @ N(zy)),if both u,-1 E N(y) and u,+2 E N ( u l ) , then zyu,u,-1 . . . u2u1u,+1u2+2‘ . . ~ , - 3 ~ , - 2 is a square-path with the required property. ((V(P)I- 1) Thus we assume that this is not the case. Then d ( u l , P ) d(y, P ) I ( V ( P )/ (If?/- 1) = 2n - 4 - IB(. Since ul !$ N ( x y ) , we have d(u1,xy) I 1, and obviously d ( y , x) = 1. It follows that + U,U,+~ + 5 -n 3 - 1I d ( u l , G) + d ( y , G) Id(u1, P ) + d ( y ,P ) + 2 I2n + - 2 - JBJ, which gives that ( B (5 n/3 - 1. We shall prove that this is impossible. Let D = { u 2 : u , + ~E N(ulu2),1 5 i 5 n - 3). Clearly, ID1 = J N p ( u 1 u 2= ) JIN(uIu2)\ { z , y j I . Since u1 @ N(xy), we have I{x,y}nN(u1u2)1 5 1. Noting that IN(u1u2)I2 d(u1u2,G)- n , we obtain that (Dl 2 d(ulu2,G ) - n - 1. By definition, B = {ZL,U,+~ : u,E D n N(zy)} and hence which gives that JBJ2 (472 - 11)/3 - ID U N(zy)J.Since u1 4 D U N(zy), ID U N(xy)I 5 IV(P)I - 1 = n - 3, and it follows that IBI 2 (n - 2)/3. This contradiction completes the I proof of Lemma 2.10. 3. AN UPPER BOUND FOR LONGEST SQUARE-CYCLES Theorem 3.1. Let C = u1u2 - - . u c u l be a chord-maximum square-cycle of a graph G with n vertices. Suppose that G - C f 0 and d ( v , G ) 2 $n for all ‘u E V ( G - C ) . Then c 5 $n,with equality only if there is a triangle T in G - C such that d ( T , G) = 2n. 248 JOURNAL OF GRAPH THEORY We first prove two additional lemmas and then go to the proof of Theorem 3.1. Recall that a cube-path contains all the 2- and 3-chords. Define an almost-cube-path to be a square-path that has at most one 3-chord absent. Lemma 3.2. Let P = x 1 x 2~ ~ ~ x p - - 2 x p -be l xap cube-path, where p 2 5. Then x1z2 is xpzp-l, xp-2xp,xpxp--2} by a squareconnected to each of the ordered edges {xp--lxp, path P’ with V(P’) = V ( P ) , and to each of the ordered edges {xp--2xp--1,xp-1xp-~} by a square-path P” with V(P”) C V ( P )and IV(P”)I = p - 1. Moreover, all of these square-paths are almost-cube-paths, possibly except for the one connecting x 1x 2 to X ~ X ~ Proof. Trivially P itself is an almost-cube-path connecting x122 to xp-lxp.Since P is a cube-path, each of the following is an almost-cube-path: 21x2 . . . Xp-3zp-22pXp-l,21~2 . . . x p ~ 3 x p - 1 x p - 2 xxp1rx 2 . . . xp-3xP--2xp-~,and x152 .. ~xp-3xp-lxp-2.Clearly, X ~ Z Z . . . ~ ~ - 3 %1zpxp-2 ~ is a square-path. This proves the lemma. I Lemma 3.3. Let C = u 1 u 2 .. . u,ul be an optimal square-cycle of G and let xy and zw be two independent edges in G - C. Suppose that d ( ~ y , u ~=u 4~ and ) xy is connected to Z7U and wz by square-paths of at least p vertices in G - C, at least one of which is an almost-cube-path. + (a) If c > 2p 3, then ~ ( z wC), 5 $c - $ p (b) If c 5 2 p + 3, then d ( z w , C ) 5 c + 2. + !. Proof. Let Q = u3u4. . . up and Q’ = ucu,_ . . . u9t be two segments of C starting at u3u4 and U , U , _ ~ , respectively, such that (i) V(Q) n V(Q’) = 0 and both IV(Q)l 5 p 1 and IV(Q’)I 5 p 1; (ii) d(u,, zw) 5 1 and d(u,t,zw) 5 1; (iii) subject to (i) and (ii), + + IV(Q)I + IV(Q‘)I is as large as possible. Letu, ~ V ( Q ) , 3 < i < q - l . S i n c e ( V ( Q ) (~ p + l , i f d ( u , , z w )=2,thend(u,+l,zw) = 0, for otherwise zw or wz is connected to ~ , u , +by~a square-path and we may replace the segment u3u4. . . u,- by a square-path in G - C to obtain a longer square-cycle. Taking into account that d ( u g ,zw)5 1, we have that d(zw,Q) F IV(Q)I1 ~, with equality only if d ( ~ , - zw) =2 (3.1) whenever d(u,, zw)= 0 with u,E V(Q). Similarly, d(z.u~, Q’) F IV(Q’)I, ~ , = 2 whenever d(u,, zw) with equality only if d ( ~ , +zw) that (3.2) =0 with u,E V(Q’). We claim = 2(d(u,+l,zw) = 2) whenever d ( u , , z w ) = 0 with with equality only if d(u,-,,zw) ut E V(Q)(uz E V(Q‘1). If d ( u 1 u 2 , z w )5 3, then (3.3) follows directly from (3.1) and (3.2). Suppose that d(ulu-2,zw) = 4. Then d(u.3, zw)= 0 or d(u,, zw)= 0, for otherwise z or w is joined to four consecutive vertices or one of u, u1zwu2u3,u,u1wzu2uy is a square-path. Without loss of generality, suppose that d ( u 3 , zw)= 0. Then, d ( z w ,Q) = d ( z w , Q - us) 5 IV(Q)I - 1, with equality only if d ( ~ , - ~ , ~= w2 )whenever d ( u , , z w ) = 0, where u, E V(Q - u 3 ) . ~ . PARTITIONING INTO TWO SQUARE CYCLES 249 This together with (3.2) gives (3.3). Let R = C - (Q u Q’ u { u l u 2 } )By . Lemma 2.l(a), 2 d ( z , R ) 5 -(RI 3 +1 2 and d(w, R ) 5 -IRI 3 + 1. (3.4) Combining with (3.3), J Substituting IRI = c - IV(Q)I - IV(Q’)I - 2 , (a) Since c > 2p + 3, the proofs of (3.1) and (3.2) also implies, by the maximality of IV(Q)I IV(Q’)I, that IV(Q)I 2 p and IV(Q‘)I L p . If both have strict inequalities, then IV(Q)l+lV(Q’)I L 2p+2 and the result follows from (3.6). Thus, without loss of generality, we assume that IV(Q)I = p , noting that IV(Q)I IV(Q’)I 2 2p. If equality does not hold in (3.31, then the result follows easily from (3.5) and (3.6). Thus we may also assume that equality holds in (3.3). If IRI f 0 (mod 31, then d ( z , R ) 5 $IRI +$ and d ( w ,R ) 5 $ IRI + $; if IRI = 0 (mod 3) and there is one strict inequality in (3.4), then d ( z w , R ) 5 $ IRI + 1. In either case, d ( z w ,R ) IIRI which implies, as seen in (3.5) and (3.61, that d ( z w ,C ) 5 $c - $ p as required. Thus we may further assume that both equalities hold in (3.4) (so \RI = 0 (mod 3)). By definition, R = uq+luq+2 . . . ugr-l. Since both equalities hold in (3.4) and by Lemma 2.l(a), we have d ( z w ,uq+luq+2) = 4. Let P be an almost-cube-path ‘ . u,ul is a squareconnecting xy to zw or wz,say to zw. Now, C‘ = u1u2Puq+luq+2. cycle. By the maximality of c, IV(P)I = p = IV(Q)1 and C’ has the same length as C. We shall arrive at a contradiction by showing that C’ has more 3-chords then C does. ( 1) + 1 > $(IRI + If d(zw,u,) # 0, say d(z,u,) = 1, then d ( z , R U {u,})= ( $ ( R+ 1) 1, contradicting Lemma 2.l(a). Thus, d ( z w ,u,,) = 0, and since equality holds in (3.3), d(zw, uq-l) = 2 . If d ( z w ,uq-2) # 0, then replacing uq by zw or wz yields a longer square, = 0, and again since equality holds in (3.3), d ( z w ,uq-3) = 2. cycle. Thus ~ ( z wuq-2) (We note that IV(Q)I = p 2 4.) We show now that there is no 3-chord incident with any vertex of { U ~ - ~ , U ~ - ~ in , UC. ~ }If E E ( G ) ,then u1u2Puq-luq+luquq+2uq+3 . . . u,ul is a square-cycle of length c + 2. If uquq-3E E ( G ) ,then u1u2Puq--3uq-luquq+1 ...u,u1is a square-cycle of length c + 3. If uq--2uq+lE E ( G ) , then u1u2Puq--3uQ-l uq-2uquq+1 . . ’ u c u l is a square-cycle of length c + 4. If uq-2uq-5E E ( G ) , then uq--5 uq-4uq-2uq-3uq-122vuq+l~q+2 . . . uq--(iuq-5 is a square-cycle of length c + 1. If u,,-1u,+2 E E ( G ) , then u ~ u ~ P u q ~ ~ u q + ~ uisqa+square-cycle 2 ~ ~ ~ u cofu length 1 c + 1. Finally, if uq-] uq-4 E E ( G ) ,then D = u q - 4 u q - 3 u q - 1 z ~ u q + l uq--5uq-4 q + ~ ~ ~is~ u a square-cycle of length c in which zuq+2 and wuqP3are 3-chords. Since we have just showed that C has no 3-chord incident with uqP2or uq and also uq-1uq+2$ E ( G ) ,the only 3-chord lost is uq-Iuq-4. However, we gain two 3-chords in D: wuq-3 and z u q f 2 . So D has more 3-chords than C, contradicting the optimality of C. This proves that there is no 3-chord incident with any vertex of { u q - 2 , u q - - 1 , u qin} C. Since P is an almost-cube-path and since u l y and z u q f 2 are 3-chords in C’, it follows that C’ has more 3-chords than C. This contradiction proves (a). + + + g, + 4 + 4, 250 JOURNAL OF GRAPH THEORY (b) Since c 5 2 p + 3 , by the maximality of IV(Q)I + IV(Q’)I we have JRI 5 1, and it follows from (3.3) that d ( z w ,C) 1. IV(Q)I + IV(Q’)I+ 3 + 21RI = c + 1 + IRI 5 c 2, as required. I + Proof of Theorem 3.2. Let H = G - C and h = 1 V ( H )1. Let K be a maximum complete subgraph in H with IV(K)I = k . By Lemma 2.7, we have k 2 4. By the maximality of K,d(K,u) < k - l f o r a l l u ~ V ( H - K ) a n d h e n c e d ( K , H ) 5 h(k-l).Ifd(K,uiui+l) 5 k + 1 for every edge U , U ~ + E~ E ( C ) ,then summing these inequalities over all i , 1 5 i L c, yields that d ( K ,G) 5 (k + 1)/2c, and consequently, (3.7) in. in which gives c 5 If equality holds, then d ( v , G) = for all v E V ( K ) So . d ( T , G ) = 2n for any triangle T in K . Therefore we assume that there is some edge U , U , + ~ E E ( C ) such that d ( K , u , ~ , +2~ )k + 2, which implies that d ( ~ , u , + ~ , e=) 4 for some edge e E E ( K ) . Let P = ~ ~ 5 .~ I 5G : ~ ~be - . a~ longest ~ ~ cube-path in H starting at some edge zlx2 with d ( x l z 2 ,u2u,+1)= 4 for some i, where p 2 k 2 4. By relabeling, we may assume i = 1. That is, d(zlz2,u1u2)= 4. Case 1. p = 4. So V ( P )induces a K4. Clearly, c 2 Ic 2 4. By Lemma 2.5(b), noting that d ( z 1 x 2 , u 1 u 2=) 4, we have that d(xlz2,G) < i c . Without loss of generality we assume that d(z2, C) < $c. If c > 2 p + 3 , then, by Lemma 3.3(a), d(53x4,C)2 $ c - 1 and hence d(x2z3z4,C) < 2c-1. By the maximality of P, d(z2x3xq,H - P ) 5 2(h-p) = 2h-8, and since V ( P )induces a K4, we have that d(z3z4,P ) = 9, and consequently, + (2h 8) + 9 = 2n, (3.8) Therefore we suppose that c 5 2p + 3 . By Lemma 3.3(b), d(x3z4,C) 5 2n 1. d ( z 2 ~ 3 ~G) 4 , < (2c - 1) a contradiction. + 2. Using 4 ~ c ~ xH4) 5 , - 2(h - l ) , 4 -n 5 ~ ( Z Q ZG) ~ ,5 c + 2 + 2(h - 1) = 2n - c, 3 in. (3.9) in, If equality, c = holds, then d(x3,G) = d(xq,G) = i n , and which gives that c 5 moreover, d(a3z4,H ) = 2(h - l ) , which implies, by the maximality of P, that d ( x 2 ,H P ) = 0. Using d ( z 2 , P )= 3 , we obtain that 4 x 2 , G) < $ c 3 I $ n $, and hence d ( z 2 ,G) = $n. Let T be the triangle on ( 5 2 , z 3 , xq}. Then d ( T , G) = 2n, as required. Case 2. p 2 5. Let T be the triangle on ( ~ ~ - z2p, - l ,z p } .If c > 2p 3 , by Lemmas 3.2 and 3.3(a), + 4 2 3 5 -c 3 - 5 -c 4 - -2p 3 Tp 3 + -,53 + -,53 + + d(xp-25p,C ) and ~ ( Z ~ - - ~ Z + IC) , L -c 4 3 - -2( P 3 - 1) + -. 5 3 Adding these inequalities yields that 2d(T, C) 5 4c-2p+5+$, which gives, since d ( T , C) is an integer, that d(T,C) 5 2c - p 2. By the maximality of P, d ( T , H - P ) 5 2(h - p ) , and using d ( T , P ) 1. 3 ( p - l ) , + 2n 5 d ( T , G) 5 2c - p + 2 + 2(h - p) + 3(p - 1) = 2n - 1. (3.10) PARTITIONING INTO TWO SQUARE CYCLES 251 This contradiction shows that c i 2 p + 3 . By Lemmas 3.2 and 3.3(b), and as seen in (3.91, we have that 4 -n 5 d(~:,-lzp,G ) 5 c 3 + 2 + 2(h - 1) = 2n, C) 5 c t 2 , (3.1 1) - C, which gives that c 5 $n with equality only if ~ ( Z , - ~ , G = )d(z,,G) = $n. If equality holds, then, by applying Lemmas 3.2 and 3.3(b) to the edge xp-2xp, we have that d ( ~ ~ ,G- )~=, d(x,, G ) = jn, and hence d ( T ,G) = 2n. This proves Theorem 3.1. We may modify the proof of Theorem 3.1 to obtain the following generalization. Theorem 3.2. Let C = ulu2 . . . u,u1 be a chord-maximum square-cycle in a graph G with n vertices. Suppose that G - C # 8 and d(v,G) 2 + r for all v E V ( G - C ) ,where r is a nonnegative real number. Then c L: $n - 2r. in Proof. Let H = G - C and h = IV(H)I. As in the proof of Theorem 3.1, let K be a maximum complete subgraph in H with IV(K)\ = lc. If d(K,u,ui+l) 5 k + 1 for every edge uiu,L+lE E ( C ) ,then, instead of (3.7), we have that J which gives c I $ n- 2 r k / ( k - 3 ) 5 f n - 2r, as required. Thus, as in the proof of Theorem 3.1, we may let P = ~ 1 ~ 2 .x. .3xp-lxp be a longest cube-path in H starting at some edge 51x2 E E ( H ) with d(zlz2,ulu2)= 4. Clearly, we still have contradictions in (3.8) and (3.10). Note that (3.9) can be included in (3.11) by allowing p = 4. Instead of (3.11), we 5 )2n - c, which gives that c 5 - 2r. This now have that $ n + 2r 5 ~ ( J : , - ~ J : , , G completes the proof of Theorem 3.2. I in 4. A LOWER BOUND FOR LONGEST SQUARE-CYCLES Theorem 4.1. If G is a graph on n vertices with S(G) 2 $n,then G has a square-cycle of length at least n/2. We need the following three lemmas in the proof of Theorem 4.1. Lemma 4.2 [4, Theorem 2.11. Let G be a graph on n vertices. If 6(G) > $n, then any two independent ordered edges are connected by a square-path in G. Lemma 4.3. Let G be a graph on n vertices with S(G) 2 $n. Let C = ~ 1 ~ 2. u. ,u . 1 be a chord-maximum square-cycle in G. Set H = G - C and h = IV(H)I. If c < h, then the following hold. (a) d ( z , C ) I $ c for all J: E v ( H ) . (b) d ( e , C ) L: (4c - 1)/3 for all e E E ( H ) . Proof. By Lemma 2.4, c 2 5. Let U Z I E E ( G ) with u E V ( C )and ZI E V ( H ) .Clearly, d ( u , N ) 2 $n-(c-l) = (2h-c)/3+1. By Lemma2.l(b), d(w,H ) 2 (2h-1)/3. Therefore, d(u, H ) + d ( v , H ) 2 h + 1+ h - c - 1 and so l N ~ ( u v )2 1 1, (4.1) 252 JOURNAL OF GRAPH THEORY with equality only if d ( u ,C) = c - 1 and d(v,C) = (2c + 1)/3. (a) If the statement is not true, let z E V ( H ) with d ( z ,C) 2 (2c + 1)/3. By Lemma 2.l(b), d ( z , C ) = (2c 1)/3 (so c 2 7). Let H’ = H - z. We first claim that there is y f V ( H ’ ) such that d ( y , ~ ~ u , +=~2) for some j , 1 5 j I c. If this is false, then d ( y , C) 5 c / 2 for all y E V ( H ’ ) and so + (4.2) Furthermore, since d ( y , ~ p , + 5 ~ )1 for ally E V ( H ’ ) ,we have that 3n 5 d(u,u,+l,G) 5 h + 1 + 2(c - l ) , which yields, using n = h + c, that c 2 ( h + 3)/2. Applying this to (4.2) yields that S(H’) 2 $ ( h- 1) 2 $ ( h- 1). By the result in [3], H’ has a hamiltonian square-cycle. This implies that H has a square-cycle of length at least h - 1, and it follows from Lemma 2.8 that H has a hamiltonian square-cycle, contradicting c < h. This shows that there is y E V ( H ’ ) such that d ( y , u j u j + l )= 2 for some j, 1 I j 5 c , as claimed. Since d ( z , C) = (2c+1)/3 and c 2 7, there is uiulLi+l E E(C-U~U,~ such + ~that ) d ( z , ~ , & u i= + 2. ~) Choose i and j such that the two edges ~ ~ u and , +u,7uj+l ~ are as close as possible. By relabeling, we may assume that i = 1, that is, d(z,u1u2)= 2. By Lemma 2.l(b) and by the choice of i and j, 3 5 j L 5. By (4.11, we may let a E N ~ ( z u 2and ) b E N~(yu,,). Case la. a # y and b $ { a , z } . By Lemma 2.5, d ( a z , H ) _> $n. - $ c = i h . Since h 2 c + 1 2 8, we see that I N ~ f ( a z )2 l 3. Let f E N ~ ( u z\ ){b,y). Now consider the subgraph H’ = H - z. For any v E V ( H ’ ) , by Lemma 2.3, if d(v,C) = (2c + 1)/3, then v z 4 E ( G ) .This implies that S(H’) > $lV(H’)l,and it follows from Lemma 4.2 that a f is connected to by by a square-path P in H‘. Then u1u2xPufufII. . . ucuI is a square cycle of length longer than C. Case lb. a f y and b = 2. By Lemma 2.3, d ( y , C ) # (2c + 1)/3, and by (4.1), I N H ( y u 3 )2 ( 2. Let z E NH(yuj)\{z). If z # a , we havecase la; if z = a,ulu2sayuju,+l . . . u,ul is a longer square-cycle. Case Ic. a # y and b = a. If I N ~ ( y u j ) 2 l 2 or I N ~ ( z u ~2) 2, l then we have either Case l a or Case l b above. Suppose that this is not the case. By (4.1), d ( z ,C) = d ( y , C) = (2c 1)/3, and by Lemma 2.4, N c ( z ) = Nc(y) and so z is joined to both u j and uj+l. Since we have equality in (4.11, d(u2,C) = c- 1 and so uLL,-1ucu2u1 is a square-path, which means that we may use xu1 as xu2 in the above arguments and derive that N H ( z u l )= { a > . Now ulu2azuju,,+1 ..’ucul is a square-cycle. Thus j = 5, and by the choice of i and j , no vertex in H is joined to both ug and u4. So d ( u g u 4 , H ) I h. Let w E { u 3 , u 4 }with d ( w , H ) 5 i h . Then d ( w , C ) 2 - i h = (3c + n ) / 6 . Using n 2 2 c + 1, we derive that d(w, C) 2 (5c 1)/6. Let P = u 4 u g u g . . . ucu1u2.It follows from Lemma 2.9 that there is a square-path P’ starting at u4u5and ending at ulu2 with V(P’)= V ( P )u {w}. Then P‘u2azu4 is a square-cycle of length c + 1. Case 2. a = y. If (N~(zu~)l 2 2, then it is one of the above cases. We thus assume that N ~ ( z u 2=) {y}. So d(u2,C) = c - 1. As in Case lc, we have that Nli(zul) = {v}. Since y cannot be joined to four consecutive vertices of C, we have j 2 4. No matter whether j = 4 or j = 5, by the choice of i , j and by Lemma 2.l(b), we always have xu3 E E ( G ) .So ulu~zyujuj+l.. .u,:u1 is a square-cycle, which implies that j = 5. As in Case lc, using d(u3u4,H ) 5 h, we obtain a longer square-cycle containing w E { u s ,u 4 } . In any case, we have a contradiction to the maximality of c. This proves (a). (b) By statement (a), d ( e , C ) 5 $c for all e E E ( H ) . If (b) is false, let zy E E ( H ) with d(zy,C) = :c (so c = 0 (mod 3) and c 2 6). By Lemma 2.5, with a proper ) y E N H ( u ~ u ~ +where I ) , 3 I t 5 5. By (4.11, labeling we have that z E N ~ ( u l u 2and + + in PARTITIONING INTO TWO SQUARE CYCLES 253 /NIJ(ZU2 ~ )2( and I N ~ ( y u t )2( 2. If there is z E V ( H ) such that N ~ ( z u=~ {z,y}, ) then u I u 2 z ~ y u t u t +.l. . uCulis a square-cycle of length at least c + 1. Otherwise, there are distinct a , b E V ( H )\ {z, y} such that a E Nfi(zu2) and b E N H ( y u t ) . By (a), d ( a z ,H ) 2 3h, 3 and since h 2 c 2 7,(N~(az)l 2 3. Similarly, l N ~ ( b y ) 2 I 3. If d ( a z , b y ) = 4, then ulu2zabyutut+l . . . uculis a longer square-cycle. Thus d(az, by) 5 3 and it follows that ) b’ E N ~ ( b y ) Let . there are distinct u’,b’ E V ( H )\ { a , b,z,y} such that u’ E N ~ ( a zand H’ = H - z - y. For any v E V ( H ) ,by Lemma 2.6, if d ( v ,C) = gc, then d(v,z y ) 5 1. This means, since c = 0 (mod 31, that S ( H ’ ) 2 - 1 > :(h - 2). By Lemma 4.2, aa‘ is connected to b’b by a square-path Q in H I . Then u1 u2xQyutut+l. . . u,ul is a longer square-cycle. This contradiction proves (b) and so the lemma. I in i c Lemma 4.4. Let G be a graph on n vertices with S(G) 2 $ 7 ~and let C = u1u2 . . . u,u1 be a chord-maximum cycle in G. Set H = G - C and h = IV(H)I. Let z E V ( H ) with d ( z , C) = max{d(v, C ) : u E V ( H ) } If . c < h, then the following hold. (a) For distinct u,v E V ( C )and y E V ( H )\{x}, if uz,yv E E ( G ) ,then uz is connected to yv through a square-path Q in H with IV(Q)I2 1. (b) z E NH(uL,_lu,) for some i, 1 I i 5 c, and if N ~ ( u ~ u ~ + ~ # ) \0, { where3 z} 2 i+2, then j - i 2 6 with equality only if d(u,+l,H ) > h/2. Proof. By applying Lemma 4.3(a) to (4.1), we have that INH(uz)) 2 2 and INH(vy)I 2 2. If N H ( U Z = ) {y, z } and N ~ ( y v = ) ( 5 ,z } for some z E V ( H ) ,then uzzyv is a squarepath and the result holds with V ( Q )= {.}. Otherwise, there are distinct w l , w2 E V ( H )\ {z, y} such that w1 c N ~ ( u zand ) wzE N ~ ( v y )If. d ( z ,C) < Zc, then, by the choice of z , S ( W ) > $h, and by Lemma 4.2, xwl is connected to way by a square-path in H and so uz is connected to yw through a square-path Q in H with {w1,w2} C V ( Q ) Thus . we assume that d ( z ,C) 2 $c, and by Lemma 4.3(a), d ( z , C) = $ c (hence c 2 6 by Lemma 2.4). Using Lemma 4.3(b), we derive that d(zwl, H ) 2 (4h + 1)/3. Since h 2 c + 1 2 7 , it follows that \ N ~ ( z w ~2 )3\ and there is z E NH(zwl) \ {w2,y}. Let H’ = H - z. For any w E V ( H ’ ) , by Lemma 4.3(b), if d ( v , C ) = gc, then vuz $! E ( G ) . This implies that S(H’) > $ ( h - l), and by Lemma 4.2, w l z is connected to w2y by a square-path in HI, which gives a square-path from uz to yu with the required property. This proves (a). If x y! NH(u,-~u,) for all i, 1 5 i 5 c, then d ( z ,C) 5 i c . By the choice of z, 2 1 2 S ( H ) 2 3n - -c = 3h+n 6 ’ ~ (4.3) and moreover, d ( H , C ) 5 ach, which implies that gnc 5 d(C,G) 5 +ch+ c(c - l ) , and hence, n 2 ;(h+2). Applying this to (4.3) gives that 6 ( H ) 2 (3h+2)/4 > qh. By the result in [3], H has a hamiltonian square-cycle, contradicting c < h. Therefore, z E NH(u,-lu2) for some i. Now let y E N ~ ( u ~ u\ ~{z} + and ~ ) choose j such that j - i is as small as possible. By statement (a), there is a square-path Q in H , where IV(Q)l 2 1, such that u,-1u2zQyu,uj+1. . . uLL,_zu,-l is a square-cycle of length at least c - ( j - i - 1)+ 3. Thus j - i 2 4. For convenience, let L = a1a2. . . at be the segment of C from u,+]to u J - l , where a1 = U , + ~ , U ~= u,+2,. . . , and t = j - i - 1. If t 2 6, the proof of part (b) is completed, and thus we assume that t 5 5. By the minimality of j - i, NH(ulul+l) = 0 for all 1 , 1 I 1 I t - 1, and then, d(alal+l,H)lh fordll,l<l5t-l. (4.4) 254 JOURNAL OF GRAPH THEORY Let A = { u E V ( L ) : d ( a , H ) 5 h/2}. By (4.4), ]A1 2 ( t - l ) / 2 with equality only if al $! A . We note that, for each a E A , d(u, C ) >_ $ n - f h = (3c + n)/6 2 (5c + 1)/6. By applying Lemma 2.9 to the graph induced by V ( C )with P = uJu,+1u3+2... u , - ~ u ,(by the minimality of j - 2, IV(P)I 2 t + 4 > 2t - 5), we obtain a square-path P’ starting at u7uJ+1and ending at u,-1uL2with V ( P ’ )= V ( P )u A. Then P’u,xQyuZLJ is a square-cycle of length at least c - t + IA( + 3, which implies that t > 5 with equality only if a1 $ A. This completes the proof of part (b), and so the lemma. a Proof of Theorem 4.1. Let C = u1u2. . . u,ul be a chord-maximum square-cycle in G. Assume, contrary to assertion, that c < n/2. By Lemma 2.4, c > 5. Set H = G - C and h = IV(H)I. So c < h. Let x E V ( H ) with d ( x , C ) = max{d(v,C) : ’u E V ( H ) } .By Lemma 4.4(b), x E N ( U , ~ , +for~ )some 2. By relabeling, we assume that z E N ( u c u l ) , and again by Lemma 4.4(b), both N ~ ( u ~\ {x} u ~=) 0 and N H ( U ~ U\ ?{x} ) = 0. If we also have N ~ ( u 2 u\ ~{z} ) = 0, then d(u2u3u4,H ) 5 h + 2 and so 2n 5 G) 5 d ( ~ 2 ~ 3 ~ 4 ,h +2 +3 ( -~ I ) = + 2~ - 1, + which gives that c 2 ( n 1)/2, a contradiction. Therefore N , Z I ( U ~\U(z} ~ ) # 0. Let y E N H ( u z u ~ ) \ { ~By } . Lemma 4.4(a), u1x is connected to yu2 and to yu4 through squarepaths Q and &‘ in H , respectively, where lV(Q)l 1 and lV(Q’)I 1. If u2u5E E ( G ) ,then u,ulxQyu2u4u5.. . u,ul is a square-cycle of length at least c+2. Thus u2u5@ E ( G ) .Since > > x cannot be joined to four consecutive vertices on C, x $ N ( u 2 u 3 )and so d(u2u3,H ) 5 h. Consequently, + which gives that c 2 n / 3 3. Using c 5 ( n - 1)/2, we obtain that n > 21, and therefore, c > 10. Now, if u3u6 E E ( G ) , then u , u l ~ Q y u 2 u 4 u ~ ~ u ~ uis~ a~ square-cycle ~ ~ u , u 1 of length at least c + 3, which is impossible. So u3u6 $ E ( G ) .Then, instead of (4.3, we have that 4 -n 5 d ( ~ 2 ~G) 3 ,5 h + 2 ( ~ 1) - 2 = 72 + c - 4, 3 and as above, c 2 13. Using Lemma 4.4(b), we derive that d ( u , ~ , + ~H, ) 5 h +1 for all j, 2 5 j 5 7, (4.6) with equality j = 7 only if d ( u 2 ,H ) > h/2. Case la. d ( u 3 , H ) 5 ( h 1)/2 and d ( u 5 , H ) 5 ( h + 1)/2. Let P = u5u6. . . u,ul (= C - u2u3uq) and let D = C - u 4 (so u2u3is the single edge of D - P). By (4.6), + D)+d d ( ~ 2 ~ 3 , ( ~ g ~D g ), > 83 -TX - 2(h 2 + 1) - 4 = 2~ + -n - 6. 3 Using n 2 2c + 1 and IV(D)I = c - 1, and furthermore, since d(u3,H ) 5 ( h + 1)/2 and d(u5,H ) 5 ( h + 1)/2, PARTITIONING INTO TWO SQUARE CYCLES 255 We have showed that u2u5 $ E ( G ) and so u5 $ N(u2u3),it follows from Lemma 2.10 that the subgraph induced by V ( D )has a hamiltonian square-path P’ starting at u2u3and ending at u,u1. Then uCu1~Q’yu4u2u3P’ is a square-cycle of length at least c + 3. Case lb. d ( u 3 , H ) 5 ( h 1 ) / 2 and d ( u 5 ,H ) > ( h 1 ) / 2 . Then by (4.61,d ( u 6 ,H ) 5 h/2. Let L = U g u 7 . . . U,UI and F = C - ~ 4 ~ We 5 . have that + d ( ~ 2 ~F3 ), + + d ( ~ g ~F7 ), 8 - 2(h 3 2 -n + 1 ) - 8 2 10lV(F)I 3 - 8 and d ( ~ yF, ) + d ( ~ gF , ) 5 2 In the proof of c 2 13, we showed that u3u6 $ E ( G ) , and so u6 f N(u2u3). It follows from Lemma 2.10 that the subgraph induced by V ( F )has a hamiltonian square-path L’ starting at ~ 2 and ~ ending 3 at u,ul. Then u,u12Q’yu4u2u3P’ is a square-cycle of length at least c + 2. Case 2. d(u3,H)> ( h + 1 ) / 2 . By (4.6), d ( u 2 , H ) 5 h/2 and d ( u q , H ) 5 h/2. Since d ( u 2 , H ) 5 h/2, we do not have equality j = 7 in (4.6) and so d ( u 7 u 8 , H ) 5 h + 1. As and u1z is connected to zu3 and to zug by square-paths before, we have z E N H(u3u5)\{~} in H . Using d(u2, H ) 5 h/2 and n 2 2c 1 , + 2 h 3c+n d(u2,C ) 2 -n - - = _ _ 3 2 6 5c+1 6 2 -. Let W = u7ulg.. . u,u1 and S = ~ 2 . . .~u6.3Since c 2 13, we have that IV(W)l = c - 5 2 8 > 2(V(S)I- 5. It follows from Lemma 2.9 that there is a square-path W’ starting at u7u8and ending at u,ulwith V ( W ’ )= V ( W )U { u 2 } , and the proof is completed by the same arguments as those used in Cases l a and lb. 5. PARTITION INTO TWO SQUARE-CYCLES Theorem 5.1. Let G be a graph on n vertices with S(G) 2 $n. Then G has two vertexdisjoint square-cycles C1 and C2 such that V ( C l )u V ( C 2 )= V ( G ) and C1 is chordmaximum. Proof. If n 5 5 , G is complete and the theorem holds with C1 = G and C2 = 0. Assume that n 2 6 and let C1 be a chord-maximum square-cycle of length c1 in G. By Lemma 2.4, c1 2 5. If c1 = n, the theorem holds with C2 = 0. We thus assume that c1 < n. Let H = G - C and h = IV(H)I. By Theorem 4.1, c1 2 h. Let C2 be a chord-maximum square-cycle of length c2 in H . If c2 = h, we are done, and thus we assume that c2 < h. Set R = H - C2 and T = IR1. By Lemma 2.8, T 2 4. If 27- 5 cl, let D = G - C2. Clearly C1 is also a chord-maximum square-cycle in D. If d(v,C2) 5 $c2 for all v E V ( R ) ,then d(v,D ) 2 $ ( n- c 2 )for all v E V ( R ) ,and it follows from Theorem 3.1 that 27- 2 cl, and so 27- = c1 and there is a triangle T in R such that d(T,D ) = 2(n - c2).By Lemma 2.6, d ( T , C2) 5 2c2 - 1. It follows that 256 JOURNAL OF GRAPH THEORY This contradiction shows that there is z E V ( R )such that d ( z , C 2 )2 (2c2 + 1)/3, which means, by Lemma 2.l(b), that d ( z , C 2 )= (2c2 + 1)/3. Let D’ = G - C2 - z. By Lemma 2.3(a), for each w E V ( R- z), if d(v,C2)= (2c2 1)/3, then wz $! E ( G ) ,which implies > $lV(D‘l for each w E V ( R- z). As before, 2 ( -~ 1) 2 el, a contradiction. that d(w,0’) If 2r 2 c1 + 1, then T 2 ( h + 1)/2 and c2 5 ( h - 1)/2. Since C2 is chord-maximum in H and by Theorem 4.1, we have that S ( H ) < $h. Thus there is x E V ( H ) such that d(z,C1)= (2c1+1)/3 (so c1 = 1 (mod 3)). Let H’ = H - x . As before, S(H’) > $lV(H’)I, and it follows from Theorem 4.1 that H’ has a square-cycle of length at least ( h - 1)/2. Therefore, c2 = ( h - 1)/2,r = ( h 1)/2, and c1 = h. Then n = 2 (mod 3) and so S(G) 2 (an 1)/3, which implies that S ( H ) 2 (2n 1)/3 - (2cl + 1)/3 = $h, a contradiction. This completes the proof of the theorem. I + + + + Note added in proofi Komlos, Siirkozy, and SzemerCdi have just used the Regularity Lemma and a new lemma they call the Blow-up Lemma to prove that P6sa’s conjecture is true for sufficiently large n, where “sufficiently large” means much more than Z1Oo. References [ 11 G. A. Dirac, Some theorems on abstract graphs. Proc. London Math Soc. 2 (1952), 68-81. [2] P. Erdos, Problem 9, Theory of Graphs and its Applications (M. Fieldler ed.), Czech. Acad. Sci. Publ., Prague (1 964), 159. [3] G. Fan and R. Haggkvist, The square of a hamiltonian cycle, SIAM J. Discrete Math., 203-212. [4] G. Fan and H. A. Kierstead, The square of paths and cycles, J. Combinat. Theory Ser: B 63 (199% 5 5 4 4 . [5] G. Fan and H. A. Kierstead, Hamiltonian square-paths, preprint, . I . Combinat. Theory Sex B, in press. (61 A. Hajnal and E. Szemeredi, Proof of a conjecture of P. Erdos, Combinatorid Theory and its Application (P. Erdos, A. Renyi, and Vera T. Sos eds), North-Holland, London (1970), 601423. [7] P. Seymour, Problem section, Combinatorics: Proceedings of the British Combinatorid Conference 1973 (T. P. McDonough and V. C. Mavron eds), Cambridge University Press, Cambridge (1974), 201-202. Received April 18, I995

1/--страниц