Ficção científica | Slovenia | افلام حروب

On the 2-extendability of planar graphs

On the 2-extendability of planar graphs

Discrete Mathematics 96 (1991) 81-99 North-Holland 81 On the 2-extendability of planar graphs D.A. Holton,” Dingjun Lou Department of Mathematics an...

2MB Sizes 1 Downloads 16 Views

Discrete Mathematics 96 (1991) 81-99 North-Holland

81

On the 2-extendability of planar graphs D.A. Holton,” Dingjun Lou Department of Mathematics and Statistics, University of Otago, Dunedin, New Zealand

Michael D. Plummer* * Department of Mathematics, Vanderbilt University, Nashville, TN 37235, USA Received 8 February 1989 Revised 4 April 1989 Dedicated 50 Pmfessor R.G. Stanton.

Abstract Holton, D.A., D. Lou and M.D. Plummer, On the 2-extendability of planar graphs, Discrete Mathematics 96 (1991) 81-99. Some suflicient conditions for the 2-extendability of k-connected k-regular (k a 3) planar graphs are given. In particular, it is proved that for k a 3, a k-connected k-regular planar graph with each cyclic cutset of sufficiently large size is 2-extendable.

1 . Introduction and terminology

All graphs in this paper are finite, undirected, connected and simple, although some parallel edge situations will occur after some contractions are made. cp contractions will be deleted. Let Y and n be However, any loops formed by the_, positive integers with n s (Y - 2)/2 and let G be a graph with Y vertices and E edges having a perfect matching. The graph G is said to be n-extendable if every matching of size n in G lies in a perfect matching of G. A graph G is called cyclically m-edge-connected if ISI 3 m for each edge cutset S of G such that there are two components in G - S each of which contains a cycle. Here S is called a q&k edge cutset. The size of a minimum cardinahty cyclic edge cutset is called the [email protected] edge connectivity of G and is denoted by clz(G). * Work supported by Grant UGC 32-635. ** Work supported by ONR Contract #NOOO14-85K.0488, NSF New Zealand - USA. Cooperative Research Grant INT-8521818 and the Universty of Otago. ()012~365X/91/$03.50 @ 1991 - Elscvicr Science Publishers B.V. All rights rcscrvcd

D.A. Holton et al.

82

In [7], Plummer introduced the concept of an n-extendable graph and proved that a graph of large minimum degree is n-extendable. In [3] and [4], Holton and Plummer proved that some k-connected k-regular graphs (k a 3) of large cyclic edge connectivity are n-extendable, which lends support to the assertion by Thomassen [9] that a graph of large girth and minimum degree at least three shares many properties with a graph of large minimum degree. According to Plummer [8], no planar graph is 3-extendable. It is then natural to ask what kind of planar graphs are 2-extendable. Holton and Plummer [3] proved (see Theorem 1 below) that a 3-connected cubic planar graph G is 2-extendable when CA(G) is large enough. Theorem 1.If G is a cubic 3-connected planar graph which is cyclically Cedge-connected and has no faces of size 4, then G is 2-extendable. Theorem 1 has the following immediate corollary. Corollary 1.If G is a cubic 3-connected planar graph which is cyclically 5-edge-connected, then G is I)-Prtendable. _ “W_ In this paper, we discuss the 2-extendability of k-connected k-regular planar graphs for k = 4,5. All terminology and notation not defined in the paper can be found in [l] or [2]. In particular, if G is a graph and S s V(G), G[S] denotes the subgraph of G induced by S. If G is a plane graph, let fi denote the number of faces of size i in the planar embedding of G and let $ denote the total number of faces in the embedding.

2. Preliminary results In this section, we present several lemmas and corollaries which will play an important role in the proofs of our main results. Note that we denote the number of odd components of G - S by o(G - S). Lemma 1. If a k-connected k-regular graph G of euen order is not 2-extendable (where k 3 2) then there are two independent edges e, and e2 which do not lie in any perfect matching and a set S c V(G) such that {e,, e2> c E(G[S]) and G(G-S)=jS]-2. 1Furthermore, i,l’N is the number of edges from the components of G - S to S, then k(lS] - 2) s N 6 klSl - 4. Proof. Suppose that G is not 2-extendable. Then there are two edges e, = u1 u1 and e2= u2v2 which do not lie in any perfect matching. Let G’ = G {Ul, JJl, u29 212). Ey Tutte’s Theorem on perfect matchings, there is a set S’ c V(G’) such that o(G’ - S’) > IS’l. Ey partity, o(G’ - S’) = IS’] + 2r, for

On the 2extendability of planar graphs

83

some r 2 1. Let .T = S’ U {u,, ul, u2, v2> and let N be the number of edges from the components of G - S to S. By the k-regularity, N < k]S] - 4. By the k-connectedness, N 3 k(o(G’ - S’)) = k(]S’l + 2r). If r 3 2, then N 2 k(lS’l + 4) = k]S], contradicting the fact that N s k]Sl - 4. So r = 1 and o(G -S) = o(G’ - S’) = IS’] + 2 = ISI- 2. Th en we have k(]S(-2)sNak(S(-4. q Lemma 2. Let G be a connected plane graph with all vertices of degree k except for r vertices. Let the degrees of the r exceptional vertices be dI , d2, . . . , d,. Then the following equation holds:

4f2+ (6-k)fs

=2[(2 - r)k + 2 d,]+x [(k - 2)j - %]fi, i=l

j24

where fi is the number of faces of size j. Proof. Let G be a connected plane graph satisfying the hypotheses of the lemma. We then have vk-rk+idi=2E=CjJ. i=l

ja2

Then and

E=

=fl

\ j; ;2.

Substituting into Euler’s Formula for plane graphs, we get 2E+rk_Cdi

[

(2-

/k 1)

-_~++=2,

k)z 6]12 +kzfi = (2 -

r)k + C dip

C[(2 - k)j + 2k]J = 2[(2 - r)k + C di], and hence

1

4h + (6 - k& = 2[ (2 - r)k + 2 di + 2 [(k - 2)j - 2k]fi, as claimed.

jZ=4

Cl

3. 243xtendability of 5conmected Sregular planar Planar graphs which are 5-connected and kegular have, in a sense, sufficiently large minimum degree for 2-extendability. In the next result, we see that all such graphs are 2-extendable.

D.A. Holton et al.

84

Theorem

2. Every konnected

S-regular planar graph G is 2-extendable.

of. Assume

(i = 1,2) be two that G is not 2-extendable and let ei =uiui independent edges in G which cannot be extended to a perfect matching. Let S and N be as in Lemma 1 and let r = (E(G[S])I. Then N = 5(S( - 2r and r 22. Since o(G - S) 2 2, S is a cutset (and hence ISI 3 5). Let Ci, . . . , C,,, be the components of G - S. Let G” be the graph obtained from G by contracting C1, - - - 3 Cm to single vertices (retaining multiple edges, but discarding any loops formed). (Note that from this point on in this paper, when we contract such a component Ci to a singleton, we will denote the resulting singleton by Ci). Then by Lemma 2, we have

4f$‘+f;‘= 2( 10 - 5~~2+ 2 di) + C (3j - lO)f 3 2( 10 + 2 (di - 5)), i=l

jZ4

i=l

where di is the degree of Ci in G” and fi”is the number of faces of size j in G”. Since every triangular face of G” uses an edge in G[S], f” < 2r. Let 6i = di - 5 (1 c i < m). Since all the digons result from contraction of Ci’s, fJ< Cy=i Si. Therefore, 4CEi 6i + 2r 2 2(1O + CEl Si) or CEi Si 2 10 - r. On the other hand, by Lemma 1, m > ISI - 2 and SlSl- 2r = N = 2 di = 2 i=l 3

(6; + 5) = 5

i=l

6i + 5m

i=l

10 - r + 5m 3 10 - r + S(lSl - 2) = 5(S( - r.

This is a contradiction.

0

4. 2-Extendability of 4-connected $-regular planar graphs For 4-connected 4-regular planar graphs the problem of determining when 2-extendability holds is more difficult as the degree of the graphs is not ‘large enough’ and the cyclic edge connectivity is not larger than six because there is always a triangle in a connected 4-regular planar graph. If a 4-regular graph G has as a subgraph the graph shown in Fig. 1 (this five-vertex graph will be called a butterfry), then G is clear!y not 2-extendable. So it makes sense to study only those 4-connected 4-regular planar graphs which do not contain a butterfly. These we will call buttefly-free 4-connected 4-regular planar graphs.

!x! I

Fig. !.

On the 2=cxtenddGCity of planar graphs

$5

Theorem 3. Let G be /I butterfly-free 4-connected 4-regular planar graph. If every cyclic edge cutset has size greater than six, except those incident with a triangle, then G is 2-extendable. Proof. Assume that G is not 2-extendable and let ei = UiVi(i = 1,2), IV and S be as in the proof of Theorem 2. Again contract the m components of G - S to singletons and call the resulting graph G”. Then by Lemma 2, we have 4fT+ 2f;‘= 2(8 - 4m + 2 di) + C (2j - 8)f i=l

ja4

=16-8m+2gdi+C(2j-8)r i=l

j34

= 16 + 2 2 (di - 4) + C (2j - 8)f’ i=l

=

j34

16 + 2 2 6i + C (2j - S)f” i=l

jZ4

or 2f;+fp8+

2 si,

i=l

where Si = di - 4. Again, since f3“s2r and f;sCzl 6i, we have 2r+2CyZl Si~f;l+2f~~8+ Ccl Si or Ccl 6i 2 8 - 2r. Furthermore, m 3 ISI - 2. Therefore, 4ISI-2r=N=C~ldi=C~l(6,+4)=C~l6,+4m~8-2r+4m > 8 - 2r + 4(lSl - 2) = 4 ISI - 2r. But then equality must hold in each inequality above. This means: (a) fi”= 0 for j 3 5, (b) G - S has no even comp._ments, (c) fT= 2r, and (d) f;= Czl 6,= 8 - 2r. (III particular, r < 4.) We now treat the three possible values of N. Case 1: N=4 ISI -4. By parity, there are now two subcases to consider. (1.1) The are eight edges from S to Cl and exactly four edges from S to Ci, for i = 2, . . . , ISI - 2. Now CZ, . . . , C,s,-2 are all singletons, for if not, it is easy to show that a cyclic cutset of size four must exist and that would contradict the cyclic connectivity hypothesis of this theorem.

86

D.A. Holton et al.

Recall from above that f;‘-- 4. Thus each edge ei lies on exactly two different triangles by 4-connectedness. So let w1 and w2 be the two distinct vertices adjacent to both u1 and v1 in G” and let w3 and w4 be the two distinct vertices adjacent to both u2 and u2 in G”. (Recall that none of these four wi’s can lie in S. Also note that we may have {w,, ~2) n (~3, ~4) # 0.) First assume w1# C, and w2# C1 in G”. Then if {wi, ~2) n (~3, ~4) # 0, there is a butterfly in G, contradicting one of the hypotheses of this theorem. On the other hand, if {wl, w2}n {w3, w4} = 0, then the induced subgraph Hi = G[{ w,, w2, ul, v,}] is a component different from a triangle in G - T where T is the set of all edges from Ii; to G - Hi. However, T is a cyclic edge cutset of size six in G, contradicting an hypothesis of the theorem. The case in which w3+ C, and w4# C, in G” is similar. So we may assume by symmetry that w1= C, = w3. Then, because f;‘= 4, ul, q, u2 and v2 are the only vertices in S adjacent to vertices of C, in G and Ci contains all the neighbors of ul , vl, u2 and v2 in G - {ul, vl, u2, v2}, except w2 and w4. So {w2, w4} is a cutset of G separating F = G[V(C,) U {ul, vl, u2, v2}] and G - F - {w2,w4;,contradicting the 4-connectedness of G. (1.2) There are six edges from S to each of C1 and C2 and there are exactly four edges from S to each Cj, for j = 3,4, . . . , ISI - 2. As in Case (1.1) we may assume that each Cj is a singleton, for j = 3,4, . . . , ISI - 2. Contracting C1 and C2, we obtain graph G”. By (d), (c) and (a) above, we know that each of C, and C2 is incident with two digons and there are exactly four vertices in S adjacent to vertices of Cj for i = 1,2. If either C1 or C2 is not a triangle, the hypothesis concerning cyclic edge cutsets is contradicted. Hence both C1 and C2 are triangles. Let x1, x2 and x3 be the vertices of C1. As there are two digons in G” incident with Ci, there is a vertex u in S adjacent to two vertices of Ci. Let Zf = G[{u, x1, x2, x3}]. Then there is a cyclic cutset of size at most six separating H from G - V(H) and once more we have a contradiction. Case2: N=4jSj-6. Again, relabeling the C’s if necessary, by parity we may assume that there are exactly six edges from S to C1 and there are exactly four edges from S to each Cj, for j=2,3,. . . , ISI - 2. As before, we may assume that each Cj, j = 2,3, . . . , ISI - 2, is a singleton. Moreover, there are exactly three edges in G[S]. Recall from (d), (c) and (a) above that f$= 2, f;‘= 6 ei = UiViq i = 1,2,3 and fi”= 0, for all j 3 5 in G”. AS f;‘= 2, there are exactly four vertices in S adjacent to vertices of C1. Let w2i-l and W2ibe the vertices adjacent to both ui and Vi for i = 1,2,3 in G”. But then it is easy to check that C1 cannot be simultaneously in {wi, w2}, { w3, w4} and ( w5, we}. Without 10s~ of generality, assume C1 is not adjacent to both ul and vl. Let aq = G[( ~1, ~2, ui, vi)]. Then there is a cyclic cutset of size at most six separating H from G - V(H), again a contradiction since H is not a triangle. Case 3: N = 4 lS( - 8.

On the 2-extendability of planar graphs

87

Fig. 2.

There are exactly four edges from S to Cj, for j = 1, 2, . a . , ISI - 2. again, as in Case (1. l), we may assume that Cj is a singleton for j = 1, . . . , 2. But from (d), (c) and (a) above, f2 = 0, fi = 8 and fi = 0 for all j 3 5. Let W, and w2 be adjacent to both u1 and u,. Let H = G[{w,, wz, ul, Then once again we have a cyclic cutset of size at most six separating H G - V(H), contradicting an hypothesis of the theorem. Cl

Once ISI -

vl)& from

Fig. 2 gives a 2-extendable 4-connected 4-regular planar graph satisf;Ing the hypotheses of Theorem 3. Indeed, an infinite family of such graphs can be constructed (of which the graph in Fig. 2 is the smallest) as follows. Let Cl2 denote the twelve-vertex configuration shown in Fig. 3(a). Take s 2 2 copies of Cl2 and join them in a

Fig. 3.

Fig. 4.

D.A. Holton et al.

Fig. 5.

ring-like fashion as indicated in Fig. 3(b). It is routine to show that the resulting graphs satisfy the properties claimed above. There are, however, many 2-extendable $-connected 4-regular planar graphs which do not satisfy the hypotheses of Theorem 3. Fig. 4 shows one such example. In the next theorem, we present an infinite family of such graphs. A graph isomorphic to the graph in Fig. 5 is called a JT (for ‘joined triangles’.) As an immediate corollary of our next theorem, we note that every 4connected 4-regular planar graph consisting of some vertex-disjoint JT’s and some other edges joining them is always 2-extendable. First, however, we will have need of the following result. Lemma 3. Suppose G is a Cregular 4-connected buttegy-free planer graph in which each vertex lies in a JT. Then any 2 JT’s in G are either identical or vertex disjoint. Proof. Suppose ST1 and ST; are two JT’s in G and that JT, # JT2. Let V(JTi) = (Ui, Vi, Xi, yi) and E(JTi) = {XiUi, XiVi, YiUip UiVi}. Let A = V(JT,) (I VP&) (1) If IAl = 1, we get a butterfly and hence a contradiction. (2) Next suppose that IAl = 2. (2.1) First suppose that A = {x,, v,}. By Lymmetry, there are three cases to consider. (2.1.1) Suppose x1 =x2 and v1 = v2. Then we get a butterfly. (2.1.2) If x1 = u-, and vu1= v2, then deg Gvl Z=Z, a contradiction. (2.1.3) So suppose x1 =x2 and v1 = y2. But then again we have that deg Gvl > 5, a contradiction. (2.2) Next suppose that A = {xl, yl}. By symmetry, there is only one case we have not yet treated. Suppose x1 =x2 and y, =y2. But then we have a butterfly. (2.3) So next we suppose that A = (ul, v,}. By symmetry, there remains only one untreated case. Suppose u1 = u2 and 2.9 = v,. But then deg (;u4 2 5, a contradiction. (3) Finally, supnose IAl = 3. (3.1) First, suppose A = {xl, ul, v,}. But by symmetry, this can happen in essentially only two different ways. (3.1.1) Suppose first that A = {x2, u2, v2). (3.1.1.1) If x1 =x2, u1 = u2 and vu1= v2, we get a separating triangle by planarity, a contradiction of 4-connectedness. l

On the 2extendability of planar graphs

89

(3.1.1.2) On the other hand, if xl = u2, u1 =x2, and V, = v2, then we get a butterfly. (3.1.2) SO suppose A = (x2,~2, ~2). But this too can happen in essentially only two different ways. (3.1.2.1) If x1 =x2, u1 =y2 and u1 = u2, we get a butterfly. (3.1.2.2) On the other hand, if x1 = u2, u1 =x2 and zll =y2, then we also get a butterfly. (3.2) So suppose A = {x1, ul, y,} = {x2, u2, y2}. Once again, we employ symmetry to point out that this can happen in only two fundamentally different ways. (3.2.1) Suppose x1 =x2, u1 = u2 and y, = y2. We then get a butterfly. (3.2.2) Finally, suppose that x1 = u2, u1 = x2 and y, = y2. Yet again we obtain a butterfly and the proof of the lemma is complete. Cl Now we are prepared to state and prove the final result of this paper. Theorem 4. Let G be a butterfly-free 4-connected 4-regular planar graph. If every vertex lies in a szzbgraph isomorphic to a JT and if the four endvertices of no two independent edges separate G into two odd components, then G is 2-extendable. Proof. Suppose G is not 2-extendable. Then there are two independent edges and e2 = u2v2 which do not lie in any perfect matching of G. Let S and e1 =ulvl N be as in Lemma 1. However, this time among all such sets S, choose one of minimum cardinafity. Again, let C,, . . . , C,s,_2 be the odd components of G - S. w4 be as before as well. Letw,,..., If there are exactly four edges joining one of the C’s to S, and Ci is not a singleton, by 4-regularity Ci has at least five vertices and the four edges from Ci to S must be independent. By hypothesis, every vertex in Ci lies in a JT which must therefore lie wholly within Ci. But since G contains no butterfly, each pair of these JT’s must be vertex disjoint and hence component Ci is even, a contradiction. So if exactly four edges join a Ci to S, that particular Ci must be a singleton. Let G” be the graph resulting from G by contracting all non-singleton components of G - S to single vertices. Exactly as in the proof of Theorem 3, we obtain the facts (a), (b), (c) and (d) listed there for graph G”. Also as in the proof of Theorem 3, there are three cases to consider. Case 1: N=4ISJ -4. (1.1) Suppose first that there are eight edges from S to C, and so there are exactly four edges from S to each Ci, for i = 2, . . . , I§1 - 2. l-lence each Cj, for must be a singleton and e, and e2 are the only edges in G [S]. i=2,...,ISI-2 Contracting Cl, we obtain graph G” which has f;‘= 4 by (d) and so there are exactly four vertices in S adjacent to vertices of C,. Let X1 = {x1, x2, x3, ~4) be this set of four vertices in S. If there is a vertex v in S - {x,, . . . ) x4, ul, q, ~2, v2}, then v does not lie on

90

D.A. Holton et al.

any triangle in G and hence is not in any JT in G, contrary to hypothesis. SO no such r~exists and hence S = {xl, x2, ~3, ~4) U &, ~1, ~2, ~2). If there is an odd component Ci different from Cl, wl, ~2, ~3 and ~4, it too cannot lie in any JT, again contrary to hypothesis. SO no such odd components exist. Hence G - S has at most five odd components and therefore ISI e 7. Let U=(ul,v *, u2, v2}. Suppose there is an xi in X1 - U from which there is just one edge to Cl. Then xi cannot lie in any triangle and hence in any JT, contrary to hypothesis. If there is an Xi E X1 - U from which there are three edges to C1, the fourth edge from xi must go to some Cj, where j # 1. But then C; = G[V(C,) U {Xi} U V(Cj)] has an odd number of vertices and thus S” = S - xi is a smaller set then S, o(G - S”) = IS”1- 2 and e, and e2 lie in S”. This contradicts the minimality of S. Thus any Xi in X1 - V has an everr number of edges joining it to C1 (i.e., either two or four). But none can send four edges to Cl, for then the remaining three Xi’s would be a cutset in G, contradicting 4-connectedness. Thus any xi E X1 - U sends exactfy two edges to Cl. (1.1.1) Suppose ISI = 7. Then without loss of generality we may assume that x1 = ul. Suppose x1 is adjacent to Cl. If xi sends exactly one edge to C1, then some xi, i = 2,3,4 must send three edges to C1, a contradiction. So x1 sends two edges to C, and hence the degree of x1 is at least five, a contradiction. (1.1.2) Suppose ISI = 6. Without loss of generality, assUBfde X1 - U = {x3, x4} and also that w1 is in C1. So {xi, x2} = {ul, vl}. But since x3 and x4 each send exactly two edges to Cl, x1 and x2 send two each also. Thus {x3, x4, w2} is a cutset in G, a contradiction. (1.1.3) Suppose ISI = 5. Without loss of generality, assume X1 - U = {x4}. Then also without loss of generality, assume x1 = ul, x2 = v 1 and x3 = u2. Since v2 is not adjacent with any vertex in C,, it must be that {w,, w4}fl V(CJ = 8. Thus we may assume that C2 - w3 and C3 = w,. Hence {wi, w2}G V( Cl). Since deg x3 = 4, there is exactly one edge from x3 to C1. Hence one of x1 and x2 sends three edges to Cl and the other sends two. But then counting edges from S to G - S, we have that v2 must send parallel edges to one of w, or w, and this contradicts the assumption that G has no digons. (1.1.4) Suppose ISI = 4. Assume, without loss of generality, that w, $ V(C,). But since deg w4 = 4, it is adjacent to both x1 and x 2. But then we have a butterfly and a contradiction. (1.2) Suppose there are six edges from C1 to S and six from C2 to S. Hence there are exactly four from :S to each of the Cj, for j = 3, . . . , IS( - 2. But then each of C3, . . . , C,s,_2 must be a singleton. Contracting C1 and C2, we obtain a graph G” in which, by (d), (c) and (a) respectively, we have f;= 4, f{=4 andfl=O for ja5. Hence by 4-connectedness, each of C, and Cz is incident with exactly two digons in G” and hence each of C1 and C2 is joined to exactly four vertices of S.

On the 2xtendability

of planar graphs

91

For i = 1, 2, denote the neighbors of Ci in S by Xi = {xqi_3, x4i_*, xqi_,, xqi). (Note that Xl and X2 are not necessarily disjoint.) Let X = X1 u X3. Finally, let X’ = X - U. AS in Case (l.l), if there is a vertex u in S x8, ul, q, u2, 2121, it Cannot lie on a triangle and we have a contradic9 (Xl, tion. Also as in Case (l.l), there can be no odd component of G - S different from Ci, C2, WI, w2, w3, w4. Hence o(G - S) s 6 and therefore 1st s 8. If there is a vertex v in S - (~1, ul, ~42,~2) from which there is at most one edge to each of Cl and C2, then v cannot lie in a triangle and again we have a contradiction. In paticular, then, S = X U U. If there is a vertex r~ in S (ul, ul, u2, v,} with three edges to Cl or C2-without loss of generality, say C,-then v is adjacent to only one other Ci. So it follows that C; = G[V(C,) lJ Iv) u v(ci)l is an odd component of G - S’, where S’ = S - {v). This contradicts the minimality of S. Also For every vertex v E S - {U1, q, u2, v2}, if u is joined to Cl by four edges, then there must be a cutset of size three, a contradiction. Similarly for C2. So for every vertex v in S - {ul, vl, u2, u2}, if it is joined to Cl at all, it must be by exactly two edges. Similarly for C2. (1.2.1) Suppose ISI = 8. (So IX’1 = 4.) By the symmetry between Cl and C2, we need only consider the following three cases. First, suppose that IX’ n Xl1 = 4, that is, X’ = {x1, x2, x3, x4}. But then by the remark above, there must be eight edges from Cl to S, a contradiction. Next, suppose that IX’ n X,1 = 3; so without loss of generality, we may assume X’ = {xl, x2, x3, x5}. Then each of x1, x2 and x3 is joined to C1 by two edges and hence {x1, x2, x3} is a 3-cutset in G, a contradiction. Finally, suppose IX’ n Xl1 = 2; so without loss of generality we may suppose X’ = (Xl, x2, x5, X6>. Now each of x1 and x2 are joined by exactly two edges to Cl. If the fifth and sixth edges joining Cl to S are adjacent (in S or in Cl), we can find a 3-cut for G containing x 1, x2 and this vertex of adjacency. So we have a contradiction. Hence the fifth and sixth edges from Cl to S are independent. Thus at most two different JT’s join vertices of Cl to S. If x1 is joined to C2, it must have c-xactly two edges to C2. Hence {x1, xs, x,} is a 3-cut in G, again a contradiction. Thus xl is not joined to Cz. By symmetry, x2 is joined to no vertex of C2 as well (and neither of x5 and xh is joined to any vertex of Cl). Now, and henceforth, let us denote by JT(v) the JT covering vertex :J, for ali v E V(G). Suppose JT(x,) = JT(x,). Then .JT(x,) covers exactly two vertices in C, and all other JT’s covering vertice, c nf vI1Cl lie entirely in C,. Thus C, is even, contradicting l

l

l

(b) . So, by Lemma 3, we may L;uppose JT(x,) and JT(x,) are vertex disjoint.

But

92

D.A. Holton et al.

then each must cover exactly three vertices in C1 and together they cover six vertices in C1. Thus again C1 is even and again we have a contradiction. Note that if IX’ nXll = 1, then IX’ nX,j = 3, and if IX’ n XII = 0, then (Xl n X,l = 4 and we repeat the above arguments on X2 and C2 in place of X1 and C1. (1.2.2) Suppose ISI = 7 and hence IX’1 = 3. First suppose that IX’ n X,1 = 3. Without loss of generality, assume that Xf n X1 = {x1, x2, x3}. But then each of these three vertices sends two edges to C1 and hence they form a 3-cut of G, a contradiction. Now suppose that IX’ n X,1 = 2. Without loss of generality, assume that IX’ n X,1 = {x1,x2}. Since C1 sends exactly six edges to S and since G is &onnected, it follows that both x3 and x4 are in U. As in Case (1.2. l), the fifth and sixth edges from C1 to S must be independent. Let the one vertex of X’ - (X, U U) be x8, since it must be a neighbor of C2 and not a neighbor of Cl. So x8 is adjacent to exactly two vertices in C2, none in Cl, and hence to two of the singleton odd components C3, C4 and C5. Say, without loss of generality, that x8 is adjacent to C3 and C4. Suppose both x1 and x2 are adjacent to C2. Then {x,, x2, x8} is a 3-cut in G, a contradiction. So at most one of x1 and x2 is adjacent to C2. Without loss of generality, assume that x1 is not adjacent to C2. First assume that x2 is not adjacent to C2 either. Now if JT(x,) = JT(x,), then each joins C, to X and as before, no other JT can join C1 to S. So IV(C,) n V(JT(x,)) n V(JT(x,))l = 2 and again it follows that C1 is even, a contradiction. So we may assume that JT(x,) and JT(x,)) are vertex disjoint. So they jointly cover six vertices of Cr and once more C, is even, a contradiction. So suppose that x1 is not adjacent to C2 but that x2 is adjacent to C2. But now x2 is adjacent to both C, and C2 by two edges to each. Thus G[C, U C2U {x2}] is an odd component of G - (S -x2) and hence G - (S -x2) has Isj - 3 = IS x21- 2 odd components, contradicting the minimality of S. Next suppose that IX’ n XII = 1. But then IX’ n X21 = 2 and we proceed as in the above case for IX’ n X,1 = 2, except we replace X1 with X2 and interchange the roles of C1 and C2 in that argument. Finally, if (X’ n X,1 = 0, if follows that IX’ n X,1 = 3 and hence that X’ n X2 is a 3-cut, a contradiction. (1.2.3) Suppose ISI = 6 and so IX’1 = 2. (1.2.3.1) First suppose that IX’ n X,1 = 2. Let X’ n XI = {xl, x2}. AS before, each of x1 and x2 sends two edges to C1. Suppose xl is adjacent to C2. Then, G[C, U C2 U {XI}] is an odd component of G - (S - x,) and this contradicts the minimahty of S. So assume that xl is not adjacent to C2 and by symmetry. that x2 is not adjacent to C2 as weii. Thus JT(x,) has three vertices in C, as does JT(x,). But then C1 is even, a contradiction. (123.2) Next, suppose IX’ n X,1 = 1. Denote X’ n X, by {x1).

On the 2qxtendability of planar graphs

93

Since IX’ n X,1 = 1, denote X’ n X2 by {x8}. As before, x1 sends exactly two edges to C1 and x 8 sends exactly two edges to C2. NOW (~2, ~3, ka} c U. Without loss of generality, assume that there are two edges from Cr to x2 and one each from C1 to x3 and x4. As before, by 4-connectedness, the two edges to x3 and x4 must be independent. Also we now know that x8 is not adjacent to C1 and so x8 is adjacent to both C3 and C4. By symmetry, at this point there are essentially two different ways we can have edges e, and e2 in I/. First, without loss of generality, assume x2 = u1 . Then, again without loss of generality, we need only treat two subcases. (1.2.3.2.1) Suppose 211=x3. Without loss of generality, let u2 =x4. NOW each of C3 and C4 lies on a JT. Of course, again by Lemma 3, they are the same or vertex disjoint. Moreover, each of these JT’s must use one of el and e2. (1.2.3.2.1.1) Suppose JT(C3) = JT(C4). Then JT(C3) cannot use edge el since deg GX2= 4, so we may assume it uses e2. Then the fourth edge from u2 must go to C2. Now since all edges incident with x4, u2 and x8 are accounted for, there must be three edges from C2 to {x1, x2, x3}. But then there is a homeomovh of K 3,3 in G” with sets of principal vertices {x,, Q; x,> and I&.. C3? C,}, a contradiction. (1.2.3.2.1.2) So suppose JT(C,) and JT(C4) are vertex disjoint. But each uses one of el and e2. Without loss of generality, suppose JT(C3) uses el and JT(C,) uses e2. Thus u1 and ~~ are adjacent to some common vertex y, E V(C,), since deg u1 = 4, Moreover, C4 is adjacent to u2 and v2. Kow JT(x,) is vertex disjoint from JT(x,) = JT(C3), so JT(Xl) has exactly three vertices or no vertices in component Cl. If it has three vertices in Cl, then it follows that Cl is even, a contradiction. So JT(x,) has no vertices in Cl and hence either two or three vertices in C2. (1.2.3.2.1.2.1) Suppose JT(x,) has exactly two vertices in C2. Then the fourth vertex of JT(x,) must be x8. But since C2 is odd, we must have JT(C,) containing one vertex of C2; call it y2. But then {xl, x8, y2} is a 3-cut in G, a contradiction. (1.2.3.2.1.2.2) So suppose that JT(x,) has exactly three vertices in C2. So JT(C,) must use exactly one vertex y2 of C2. But then again {x1, x8, y2} is a hut in G, a contradiction. (1.2.3.2.2) So suppose that u1 $ {x3, x4}. So {x3, x4} = {u2, u2}; without loss of generality, suppose x3 = u2 and x4 = 212. Without loss of generality, we may assume that JT(C3) uses edge et. But then deg x2 = 4 implies that JT(C3) meets Cl. But that is impossible, since u1 is not adjacent to any vertex in Cl. (1.233) Suppose IX’ n X,1 = 0. Then IX’ n X21= 2. So we proceed as in Case (1.2.3.1), except we interchange the roles of X1 and X2 and those of Cl and C2. (1.2.4) So suppose ISI = 5. Thus IX’1 = 1. Without loss of generality, suppose X’ = {x,}. So as before, we have exactly two edges from x1 to C I. Suppose x1 is adjacent to C2 and hence to exactly two vertices in C2. Then S’ = S-i {xl} has the property that G - S’ has two odd

94

D.A. Holton et al.

Fig. 6.

components (one of which is G[V(C,) U V(C,) U {x,}] and the other is C,). So G - S’ has IS’] - 2 odd components and (e,, e,} c_ E(G[S’]). Thus once again we contradict the minimality of the choice of set S. (1.2.5) Suppose 1st = 4. So X’ = 0 and S = U. But then the endvertices of el and e2 separate G into two odd components, a contradiction. This completes Case 1. Case 2: N = 4 ]S] - 6. We may assume that there are six edges from S to C, and exactly four edges from S to each of C2, C3, . . . , Cls,+ So each of Cz, . . . , C,s,-2 is a singleton. Also there are exactly three edges ei = UiUi, i = 1, 2,3 in G[S]. Let U = @I, U?,Pu3, Vl, v2,v3). Upon contracting component C, to a single vertex we obtain graph G” in which f;’ = 2, f;’ = 6 and J” = 0 for j 2 5, by (d), (c) and (a) respectively. Since f;= 2, there are exactly four vertices of attachment for C1 in S. Again denote them by x1, x2, x3 and x4. Let wl, . . . , w6 be as in the proof of Case 2 of Theorem 3.

On the 2qxtendability

of planar graphs

95

Let ?JE s - E/. Since ?J must lie on a triangle in G, 7~must be adjacent to at least two vertices of Cl. If IJ is adjacent to three vertices in C, , it is adjacent to precisely one of Cz, . . . , cl~l-~~ Suppose it is Cj. Then, if C; = G[V(C,) u V(CJ U {v}], then if S’ = S - {v}, set S’ contains edges e, , e2 and e3, graph G -S’ has ISI -3~ IS’1- 2 odd components (one of which is C;) and this contradicts the minimality of S. It v is adjacent to four vertices in C1, then there must be a 3-cut in G separating C, from the rest of G and this is a contradiction of the 4-connectedness of G. Hence, if v is any vertex in S - U which is adjacent to C,, it must send exuctZy two edges to C1. Also, since f;‘= 6, if there is any singleton odd component Ci different from Wl, * 9 w6, it cannot lie on a JT. So it follows that o(G - S) s 7 and hence that ISI < 9. Also since f;‘= 6, each of el, e2 and e3 lies on exactly two triangles. But then by 4-regularity, it follows that these three edges are vertex disjoint and thus that ISI 2 6. (2.1) Suppose ISI = 9. Now since every vertex of S - U lies on a triangle, it is adjacent to C1 and, therefore, by the above remark, it sends exactly two edges to component C1. But then S - U is a 3-cut in G, a contradiction. (2.2) Suppose ISI = 8. Without loss of generality, assume that S - U = {x,, x2}. Since each of the singleton odd components C2, . . . , C,s,_2 must lie on a triangle in G” and each of these triangles must contain one of the edges e,, we may assume without loss of generality that the two triangles cuntain’ng e, also contain vertices C, and Cz, the two containing edge e2 contain C3 and C4 and the two containing edge e3 contain cs and C6. But now back in the parent graph G, vertices C3, C4, C5 and C6 lie in unique JT’s which must be spanned by C3, C4 and the two ends of edge e, and by Cs, C6 and the two ends of edge e2 respectively. Also C2 lies in a unique triangle consisting of C2 and the two ends of edge e,. But then C2 lies in a unique JT which must use the two edges to C1 which are not incident with vertices x1 and x2. Call these two edges fi and X. But then fi and fi have a common endvertex y in C1. But then {x,, x2, y } is a 3-cut in G, a contradiction. (2.3) Suppose ISI = 7. Then at most two JT(Ci)‘S (i 2 2) send edges to C,, since the total number of edges into C, from S is six. Suppose that two JT(C;)‘s (i 2 2) send edges into Cl Then G has a 3-cut consisting of x1 and two vertices in C,. Suppose next that exactly one JT(C,) (i 3 2)-say JT(C,)-has a vertex in Cl. Then relabeling if necessary, we may assume that JT(Cq) = JT(Cs) uses edge e3 and then odd component C3 lies in no JT, a contradiction. SO suppose that no JT(C,) (i a 2) has vertices in C,. Without loss of generality, we may suppose that JT(C2) = JT(C3) uses edge e2 and that JT(C4) = JTG) uses edge e3. Then the JT using edge el has exactly two vertices in Cl; call them a and l

l

96

D.A. Ho/ton et al.

fi. But then {x,, a, /3} is a 3-cut in G, a contradiction. (2.4) Suppose (S( = 6. Since the JT(C,), i 2 2, must be vertex disjoint, at most one of them uses two of C2, C, and Cb. First suppose exactly one JT(C,) uses two of Cz, C3 and Cq. Relabeling, if necessary, we may assume that JT(Q = JT( C,) and that JT( C,) uses edge e3. Then JT(C*) uses edge e2 say, and one vertex y, of Cl. Now consider JT(u,) and JT(v,). First suppose that JT(u,) = JT(v,). Also suppose first that JT(u ,) uses edge e,. Then {ur, v, , y,) is a 3-cut in G. So suppose that JT(u ,) does not use edge e, . Then JT(u,) uses exactly two vertices in Cl and again u, , y,} is a 3-cut in G. So suppose that JT(u,) and JT(v,) are vertex disjoint. Then neither uses edge e, and so together they use six distinct vertices in Cl. But then again {u, , II,, yl} is a 3-cut in G. SO suppose that no JT(Ci), (i 22), uses two of the vertices C2, Cs and C4. Then JT(G,), JT(C,) and JT(C4) are vertex disjoint and each uses a different vertex of Cl, say Ci casesyi, for i = 2, 3,4. But then either {yz, y3, y4} is a 3-cut in G, which is impossible, or IV(C,)l = 3. But if Cl has only three vertices, no vertex in C! can be covered by a JT, a contradiction. Case 3: N = 4 ISI - 8. Note that there are exactly four edges from each of Cl, . . . , C,s,-2 to S and G[S] contains four edges ei = U;Vi for i = 1, . . . , 4. So all of Cl, . . . , C,s,_2 are singletons. Note that by (c) and (a) respectively, we have f3 = 8 and fi = 0, i 2 5. Hence each ei lies in exactly two triangles in G. (3.1) Suppose two of the ei’s share a vertex; without loss of generality suppose e, = ab and e2 = bc. (3.1.1) Suppose also that a is adjacent to c, say ac = es. So e, lies on triangle abca and one other triangle which uses one of the C’s-say Cl. If c is adjacent to Cl, then acC,a must be a separating triangle in G, a contradiction. So we may assume that c is not adjacent to C1. So let the second triangle using e2 be abC2a, where C2 f Cl. But then (a, b, c, Cl, C,} must span a butterAy, contrary to hypothesis. So, by symmetry, no three of the ei’s can form a triangle. (3.1.2) So assume that a is not adjacent to c. Let the two triangles using edge ei be abC,a and abC2a. Since G contains no butterfly, we have that c is adjacent to neither C1 and C2. But then since deg Gb = 4 and N(b) = {a, c, Cl, C,}, edge e2 cannot lie cn a triangle in G, a contradiction. (3.2) So we may assum.e that no two ei’s share a vertex; that is, {e, , e2, e3, e,} are vertex disjoint. Since every vertex of G must lie on a triangle, if follows that every vertex of S must be an endvertex of one of the ei’s. Thus ISI = 8 and hence o(G-S)=6. Now all triangles, and hence all JT’s, in G each must use exactly one of the ei’s

{u,,

On the 2extendability of planar graphs

97

Fig. 7.

and hence two of the singleton odd components Cl, . . . , C6. But this is clearly 0 impossible and the proof of the theorem is complete.

5. Concluding remarks Let us close by offering a few remarks as to the sharpness of the results in this paper. Remark 1. According to [5], there are non-2-extendable k-connected k-regular graphs, for k = 3, 4, 5, with cyclic edge connectivity arbitrarily large. So in this sense, planarity is necessary in the hypotheses of Theorems 1,2 and 3. Fig. 7 shows a nonplanar graph in which e, and e2 cannot be extended to a perfect matching, whi+dfiIshows that Theorem 4 also requires planarity in the hypothesis. Remark 2. Fig. 8 shows a cyclically &edge-connected butterfly-free non-2extendable 4-connected 4-regular planar graph in which each cyclic edge cutset has size greater than six, except the edges incident with a triangle and the edges incident with a JT. Hence this graph shows the sharpness of Theorem 3 v&h respect to the cyclic edge connectivity assumption in the hypothesis.

Fig. 8.

D.A. Ho&on et al.

04 Fig. 9.

Remark 3. Fig. 8 also shows the sharpness of Theorem 4 with respect to the JT covering assumption, as every vertex in the graph lies in a JT, with the exception of exactly two. Remark 4. Fig. 9 shags how to build a cyclically 4-edge-connected non-2 extendable planar graph which consists of disjoint triangles and some other edges. Substituting the graph in Fig. 9(b) for each of C, and C2 in Fig. 9(a) by identifying edges as shown, we get a non-2-extendable 4-connected 4-regular planar graph in which edges e, and e2 do not lie in any perfect matching. So in the hypothesis of Theorem 4 we cannot change the demand that G be vertex partitionable into JT’s to say instead that G be vertex partitionable into triangles. emark 5. Fig. 6 shows a butterfly-free 4-connected 4-regular planar graph in which every vertex lies in a subgraph isomorphic to a JT. However, the four endvertices of edges e1 and e2 separate G into two odd components and hence e,

On the 2qxtendability of planar graphs

99

and e2 lie in no perfect matching in G. This graph shows, in particular, that the last hypothesis in Theorem 4 is not derivable from the others.

Acknowledgement The authors wish to thank the referee for his thorough reading of this paper and for his suggestions which, in particular, considerably shortened the original proof of Theorem 4.

References J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan, London, 1976). F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969). ;;; D.A. Holton and M.D. Plummer, 2-extendability in 3polytope5, (Combinatorics. Eger, Hungary, 1987) Colloq. Math. Sot. J. Bolyai 52, Akademiai Kiadb, Budapest (1988) 281-300. PI D.A. Holton and M.D. piummer, Matching extension and connectivity in graphs II, Proc. Sixth International Conference on the Theory and Applications of Graphs, Kalamazoo, 1988 (Wiley) to appear. PI D. Lou and D.A. Holton, Lower bound of cyclic edge connectivity for n-extendability of regular graphs (1988) submitted. 161i. Lo&z and M.D. Plummer, Matching theory, Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986). PI M.D. Plummer, On n-extendable graphs, Discrete Math. 31 (1980) 201-210. PI M.D. Plummer, A theorem on matchings in the plane, Graph Theory in Memory of G-A. Dirac, Ann. Discrete Math. 41 (North-Holland, Amsterdam, 1989) 347-354. PI C. Thomassen, Girth in graphs, J. Combin. Theory Ser. B 35 (1983) 129-141.

PI