Independent Sets In Triangle-Free Cubic Planar Graphs POST-REFEREED DRAFT #2 Christopher Carl Heckman1 checkman@math.asu.edu Department of Mathematics and Statistics, Arizona State University, Tempe, AZ, 85287–1804 Robin Thomas1 2 thomas@math.gatech.edu School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, 30332–0160 Abstract: We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 83 n. This was suggested and later conjectured by Albertson, Bollobás, and Tucker. 1. Introduction In [1], Albertson, Bollobás and Tucker showed that every triangle-free 3-regular graph on v vertices has an independent set with size strictly larger than 13 v. The lower bound was later improved by Staton [14] 5 (with a shorter proof found later by Fraughnaugh [10] and an even shorter one by the authors [6]) to 14 v for triangle-free graphs of maximum degree at most three. This is tight, because, as noted by Fajtlowicz [3], the generalized Petersen graph P (7, 2) has 14 vertices, no triangles, and no independent set with size six. (There is another such graph with the same independence ratio, found by Stephen Locke.) In that same paper, Albertson, Bollobás and Tucker conjectured that every triangle-free planar graph has an independent set with size strictly larger than 13 v. This conjecture was proved by Steinberg and Tovey [15], who showed that every triangle-free planar   graph on v vertices has a “non-equitable” 3-coloring, and thus an independent set with size at least 31 v + 1. This is tight for an infinite family of planar graphs of maximum degree four, originally found by Jones [9]. For triangle-free 3-regular planar graphs with v vertices, Albertson, Bollobás and Tucker [1] stated that “it seems likely” that there is an independent set with size at least sv, where s > 31 might be as large as 38 . According to Albertson [private communication], later they conjectured that this is indeed true for s = 38 . In this paper we prove their conjecture: Theorem 1.1. Every triangle-free planar graph G of maximum degree three has an independent set with size at least 38 V (G) . The constant 83 is best possible, even for planar graphs with no cycles of length less than five, as shown, for instance, by the graph depicted in Figure 1. Carsten Thomassen [private communication] kindly informed the authors that it follows from Tutte’s theorem [16] or from [11] that every cyclically 4-connected cubic planar graph on n vertices has an independent set of size at least 3n/8 − 1/2. However, we do not see a way to deduce Theorem 1.1 from this result. 1 2 Partially supported by NSA under Grant No. MDA904-98-1-0517 Partially supported by NSF under Grant No. DMS-9623031 1 ❩ Figure 1. A planar graph of girth 5 with independence ratio 3 8 We now present to the reader two conjectures which would also imply Theorem 1.1. The first is due to Fraughnaugh and Locke. In [4], they conjectured that if the assumption of planarity in Theorem 1.1 is weakened to the condition that G has no subgraph isomorphic to one of six fixed (nonplanar) graphs, then G has an independent set with size at least 38 V (G) . The second conjecture involves generalizing the chromatic number of a graph. The fractional chromatic number of a graph G is the infimum of all ab such that to every vertex of G one can assign a subset of {1, 2, . . . , a} with size b in such a way that adjacent vertices are assigned disjoint sets. It follows that the infimum is attained, because it is the optimum value of a certain linear program with rational data. The linear program is the linear programming relaxation of a certain integer program whose optimum is the chromatic number. It appears that the fractional chromatic number was first introduced in [8]; a more thorough reference is Scheinerman and Ullman’s book [13]. We conjecture the following. Conjecture. Every triangle-free planar graph with maximum degree at most three has fractional chromatic number at most 38 . This conjecture generalizes Theorem 1.1 in the following way: Let w be an assignment of positive real numbers to the vertices of G, and define w(S) to be the sum of the weights of all vertices in S. If the fractional chromatic number of G is r, then there is an independent set I of G with weight at least 1r that of V (G); that is, w(I) ≥ 1r w(V (G)), for some independent set I. Giving every vertex equal weight thus would imply Theorem 1.1. We remark that Hell and Zhu [7] have proven that if G has no K4 -minor and is triangle-free, then the “circular chromatic number” of G (which is at least as large as the fractional chromatic number of G) is at most 38 . Since all graphs which have no K4 -minor are planar, this implies that a counterexample to our conjecture must contain a subdivision of K4 . Pirnazar and Ullman [12] have given bounds on the fractional chromatic number of planar graphs in terms of their girth, but without any conditions on their maximum degree. For instance, the fractional chromatic number of any planar graph of girth 4 is at most 3, and the constant 3 is best possible, because of a family of graphs in [9]; however, these graphs have maximum degree four. Also shown in [12] is a family of planar graphs of girth five (once again having vertices of degree four) whose fractional chromatic number converges to 11 4 . The authors have also conjectured [6] that the fractional chromatic number for triangle-free cubic graphs is at most 14 5 . The best result related to these conjectures is by Hatami and Zhu [5], which states that the fractional 3 . chromatic number of a triangle-free graph with maximum degree at most three is at most 3 − 64 2 2. Statement of the Main Theorem We will prove Theorem 1.1 by induction. In order to make our induction argument work we prove a stronger statement, Theorem 2.1, which we now introduce. Intuitively, vertices of degree less than three should make it easier to find a large independent set, and so one would expect a stronger result for graphs with vertices of degree less than three. Ideally, we would like to prove that every triangle-free of  planar graph G  3 1 maximum degree at most three has an independent set with size at least 8 V (G) + 24 3 V (G) −2 E(G) . The quantity 3 V (G) − 2 E(G) , called the deficiency of G, measures how close the graph G is to being 1 is as follows. Assume that 3-regular and is always non-negative. The reason for our choice of the constant 24 we are trying to prove that every triangle-free planar graph G has an independent set of size as specified above, suppose that G is a minimal counterexample, and assume that G is 3-regular. Then G has no cycles of length four. For suppose that v1 v2 v3 v4 is a 4-cycle in G. Then the graph obtained from G by deleting v1 and v3 and all their neighbors has an independent set of the required size by the minimality of G, and by adding v1 and v3 to this set we obtain a required independent set in G, a contradiction. Unfortunately, the above strengthening is false, but we were able to find a way to cope with the counterexamples. There are two kinds of counterexamples to the stronger version: very bad ones, and moderately bad ones. The very bad ones are a subset of what we call “link graphs.” Luckily, it can be shown that no link graph L is a subgraph of a minimal counterexample to Theorem 1.1, for otherwise L “links” together two pieces of a smaller counterexample. Thus we only prove the stronger version for graphs not containing link graphs. The moderately bad counterexamples fail the stronger version only by a small amount, and so it suffices to add an additive correction factor for each component of G that is a moderately bad counterexample. Those will be called “difficult” graphs (as in [6]). Actually, there is a third kind of counterexample, called Kayak, which falls somewhere in between link graphs and difficult graphs, which can be treated as either of the two. We chose to treat it in the same way as link graphs, because that way some of the lemmas are easier to state. We will need a large amount of definitions before we can state Theorem 2.1, and so let us describe the theorem informally first. We will define a graph to be valid if it is planar, has maximum degree at most three, and has no subgraph that is a triangle, a link graph or the graph depicted in Figure 5 below. For every graph H we will define λ(H) to be the number of components of H that are difficult graphs. Theorem 2.1 then asserts that 1 1 d− 12 λ(G), where d is the defievery valid graph G on n vertices has an independent set of size at least 38 n+ 24 ciency of G. It is fairly easy and will be shown at the end of Section 3 that Theorem 2.1 implies Theorem 1.1. But how do we prove Theorem 2.1? That is a long story, but let us make a brief and informal outline here. Suppose the result is false, and let G be a minimal counterexample. A typical step in the proof will consist of deleting a set X of vertices, and using the fact that G\X satisfies the theorem to get an independent set I in G\X of the appropriate size. We then combine I with a suitable subset of X to get an independent set in G, and demonstrate that way that G satisfies the conclusion of the theorem after all, a contradiction. So, for instance, X could consist of a vertex v and all its neighbors, and then we can take I ∪ {v} as the independent set of G. Unfortunately, this choice of X is of limited use, and we will have to make more sophisticated selections. Sometimes we will need to also add edges to the graph G\X, and that poses additional complications, because adding edges might create triangles or the other graphs that were excluded. We set up machinery for the applications of such arguments in Section 4, after showing some useful properties of difficult and link graphs in Section 3. Three easy properties of a minimal counterexample G are shown in Section 5, while in Section 6 we show that G has no cycles of length four. If v1 v2 v3 v4 is a cycle of length four, then letting X consist of v1 , v3 and all their neighbors works very well. The above argument with I ∪ {v1 , v3 } shows that G\X has a difficult component, and that additional information can be exploited to derive a contradiction. Similarly, in Section 7, we show that G is 3-regular, and in Section 8 we are able to deduce that G is 3-connected. This shows that all pentagons are facial, and in Section 9, we show that facial pentagons are surrounded by facial pentagons. This implies that G must be the dodecahedron graph, which satisfies Theorem 2.1. This final contradiction ends the proof. That was a brief outline, and now it is time to be precise. We need some definitions in order to state Theorem 2.1. All graphs in this paper are finite and have no loops or multiple edges. By a block we mean a graph G such that G\v is connected for every vertex v ∈ V (G). A block of a graph G is a maximal subgraph 3 ❇❆ ❈❉ ❊ of G that is a block. A graph is 2-connected if it is a block on at least three vertices. Suppose that a triangle-free planar graph G with maximum degree three has a vertex v2 of degree two, both of whose neighbors v1 and v3 have degree three, and the rest of the vertices of degree two in G induce a matching with size two. Suppose further that the graph H = G \ {v1 , v2 , v3 } has exactly one cut-edge e, and let D1 and D2 be the components of H \ e. Lastly, suppose that exactly two edges connect {v1 , v3 } to each Di . Then we will call G a sum of D1 and D2 . (See Figure 2.) (Note that all possible sums of pentagons are called G2 graphs in [10].) D1 D2 D1 D2 v1 v2 v1 v3 v2 v3 Figure 2. A Sum of D1 and D2 A graph H will be called an 8-augmentation of the graph D if it can be obtained from D by the following construction: Let the vertices u and v have degree two in D, and suppose that uvwx is a path in D. Then H is obtained from D by deleting the edge wx and adding the paths wy1 y2 x, y1 y3 y4 v, y4 y5 y6 y2 , y3 y7 y8 y5 and the edge uy6 , where the vertices y1 , . . . , y8 are distinct new vertices. (See Figure 3.) w w x x y1 y2 y7 y3 7−→ y8 y6 y4 y5 u u v v Figure 3. An 8-augmentation Finally, suppose that a triangle-free planar graph G of maximum degree three has a vertex y2 of degree two, one of the neighbors y1 of y2 has degree two, and the other neighbor y3 has degree three. Suppose further that the graph D = G \ {y1 , y2 , y3 } has exactly five vertices of degree two, and that every vertex of G with degree two in G has exactly one neighbor which is also a vertex of degree two in G. Then we will call G a 3-augmentation of D. (See Figure 4.) y1 v3 D v1 v2 y3 y2 Figure 4. A 3-augmentation of D 4 ❋ A triangle-free planar graph G of maximum degree three will be said to be a difficult block if it is isomorphic to a pentagon (a cycle of length five), a sum of two smaller difficult blocks, or an 8-augmentation of a smaller difficult block. A graph G will be said to be difficult if every component of G \ F is a difficult block, where F is the set of all cut-edges of G. Given a graph G, we define λ(G) to be the number of components of G which are difficult. A triangle-free planar graph with maximum degree three will be said to be a link graph if it is a 3-augmentation of a difficult block or an 8-augmentation of a smaller link graph. A graph H will be said to be a forbidden graph if it is a triangle, a link graph, or Kayak, the graph shown in Figure 5. Lastly, a graph G will be said to be valid if it is planar, has maximum degree at most 3, and has no subgraphs which are forbidden graphs. Figure 5. The Graph Kayak Note that Kayak has an independent set with size six disjoint from its vertices of degree two; this will allow a simplification of the proofs of some of the lemmas that follow. Now we can state our main result: Theorem 2.1. Every valid graph with n vertices and e edges has an independent set with size at least 1 1 3 1 1 1 n− e− λ(G) = n + (3n − 2e) − λ(G). 2 12 12 8 24 12 The remainder of this paper is devoted to the proof of Theorem 2.1. For the remainder of this paper, we will let G be a minimal counterexample, that is, a valid graph that does not satisfy the conclusion of Theorem 2.1, such that any valid graph with strictly fewer vertices than G satisfies Theorem 2.1. We will use standard graph theory terms unless otherwise noted; see [2], for example. Given an independent set I in a graph G, we will let NG (I) be the set of all vertices adjacent to some vertex in I; when the graph G is implied, we will omit the subscript. Given a set X of vertices of G, δG (X) will denote the set of all edges with exactly one end in X. Again, we will omit the subscript when the graph is implied; we will also let δ(H) = δ(V (H)) if H is a subgraph of G. The set N (I) is often called the boundary of I, and δ(X) the coboundary of X. 3. Difficult Graphs and Link Graphs We start with the proof of some useful properties of difficult graphs and link graphs. A difficult block D will be said to be k-accessible if it has k vertices of degree two which are incident to a common face in some planar embedding of D. We will also define b(D) to be the number of difficult blocks of a difficult graph D. A big set of a difficult graph D will be an independent set with size at least 1 3 8 V (D) + 8 b(D). We now present some elementary facts about difficult graphs. Lemma 3.1. Let D be a difficult block. Then: (i) The graph D has exactly five vertices of degree two and none of degree strictly less than two, and hence
D has precisely 12 3 V (D) − 5 edges; (ii) If D is not a pentagon, then the vertices of degree two induce a matching with size two and one isolated vertex; (iii) The graph D is 2-connected; (iv) For every pair of nonadjacent vertices u, v of degree two of D, there is a big set I such that the vertices of degree two in I are also in {u, v}; (v) For every pair of vertices of degree two of D, there is a big set disjoint from them; (vi) If D is 5-accessible, then D is a pentagon; and (vii) If D is 4-accessible, then D is a pentagon or the graph G4 (shown in Figure 6), which is a sum of two pentagons. 5 ● Figure 6. The Graph G4 Proof : The proof is by induction on the number of vertices in D. Part (i) is a direct result of the definition of a difficult block and counting; (ii) follows from the definition and keeping track of where the vertices of degree two are; (iii) follows by finding an ear decomposition. Part (iv) implies (v), for the following reason: Let v1 , v2 , v3 , v4 and v5 be the five vertices of degree two in D, and suppose that a big set disjoint from {v1 , v2 } is desired. The graph D cannot contain the edges v3 v4 , v3 v5 , and v4 v5 , since it is triangle-free. Hence, two of the vertices among v3 , v4 and v5 are nonadjacent. If v3 and v4 are nonadjacent, then there is a big set I whose only vertices of degree two are v3 and v4 ; this big set does not contain v1 or v2 , as desired. To prove (iv), it suffices to consider four cases: where D is a pentagon (which is trivial); where D is the sum of D1 and D2 (which is actually two cases); and where D is the 8-augmentation of D1 , another difficult block. The second and third cases have two sub-cases: where u and v are in D1 and D2 , and where u is in D1 and v is v2 . (This follows from (ii), since u and v are nonadjacent.) In the case where u is a vertex of D1 and v is a vertex of D2 , let u1 , u2 , and u3 be the vertices of D1 which have degree three in D and degree two in D1 , and define y1 , y2 , and y3 similarly for D2 , v2 the vertex of degree two with two neighbors (v1 and v3 ) of degree three, and suppose v1 is adjacent to two vertices in D1 . The vertex u is adjacent to at most one of u1 , u2 and u3 , since it has degree two in D (and one of its neighbors has degree two in D as well). Hence we may assume that u is not adjacent to u1 and u2 , and that v is not adjacent to y1 and y2 . We may assume (by relabeling) that u1 is not adjacent to any vertices in D2 . Then let I1 be a big set of D1 whose only two vertices of degree two are u and u1 . Let y1 be the vertex (in D2 ) not adjacent to v and not adjacent to v3 (at least one such vertex exists). Then let I2 be a big set of D2 whose only two vertices of degree two are v and y1 . Then I1 ∪ I2 ∪ {v3 } is a big set of D whose only vertices of degree two are u and v. Other cases and subcases can be handled in a similar manner. Part (vi) can be handled in the same way as (vii), which is proven below. To show (vii), suppose that D is a sum of two difficult blocks D1 and D2 , and suppose further that D is 4-accessible. Let X be the set of four vertices of D of degree two that are incident with a common face. It follows that X ∩ V (D1 ) = X ∩ V (D2 ) = 2. We deduce that both D1 and D2 are 5-accessible, and hence both are pentagons by induction. Since D is planar, triangle-free, and has maximum degree three, we deduce that D is isomorphic to G4 , as desired. It is not difficult to see that if D is an 8-augmentation of a difficult block, then D is not 4-accessible. Lemma 3.2. A difficult graph D has exactly vertices of degree two. Proof : 3 2 V (D) − 23 b(D) − λ(D) edges, a big set, and at least 5λ(D) This follows from Lemma 3.1(i) and Lemma 3.1(v) by induction. We will define a big set for a link graph L to be an independent set of L with size at least 38 V (L) . (Note that no graph can be both a difficult block and a link graph by Lemma 3.1(i) and Lemma 3.3(i); hence the size of a big set is well-defined.) A vertex of degree two in a link graph will be called a linking vertex . We present some elementary properties of link graphs: 6 Lemma 3.3. Let L be a link graph. Then:
(i) The graph L has exactly four vertices of degree two and 21 3 V (L) − 4 edges; (ii) Every linking vertex of L is adjacent to exactly one other linking vertex of L. (iii) The graph L is 2-connected; (iv) For every linking vertex w of L, there is a big set Iw of L such that w is the only linking vertex of L in Iw ; and (v) In every planar embedding of L, there is no face incident with all four linking vertices of L. Proof : The proof follows by induction on V (L) , using Lemma 3.1. Part (i) is a direct result of the definition of a difficult block and counting; (ii) follows from the definition; (iii) follows by finding an ear decomposition of L. To show (iv), suppose L is an 3-augmentation of a difficult block D; i.e., suppose L \ {y1 , y2 , y3 } is isomorphic to D, where the neighbors of y2 are y1 and y3 , and y3 has degree three. If the linking vertex w is y1 or y2 , then the union of a big set of D using only the neighbors of y3 (which are nonadjacent) and {w} is a big set of L. If w is a vertex of D and y1 is not adjacent to a neighbor of w, then a big set of D using only w and the neighbor of y1 in D (along with the vertex y3 ) is a big set of L. Hence, w is adjacent to the vertex adjacent to y1 . But since w is adjacent to two vertices in D which have degree two in D, D must be a pentagon (by Lemma 3.1(ii)), and y3 is adjacent to two adjacent vertices of D, a contradiction, because L was assumed to be triangle-free. A similar analysis works if L is an 8-augmentation of another link graph. Lastly, to show (v): If L is a 3-augmentation of a difficult block D, and there is a planar embedding violating (v), the embedding also implies that D is 5-accessible (and thus a pentagon, by Lemma 3.1(vi)); but because L is triangle-free, L must be isomorphic to a unique graph (Λ0 , shown in Figure 7) which satisfies (v). If L is an 8-augmentation of another link graph, the argument is straightforward. ❍■ We now present two specific link graphs which will show up in the proofs of Lemma 6.3 and Lemma 7.1. Lemma 3.4. The graphs Λ0 and Λ1 shown in Figure 7 are link graphs. Figure 7. The Graphs Λ0 and Λ1 . Proof : The graph Λ0 is a 3-augmentation of a pentagon. The graph Λ1 is a 3-augmentation of a sum of two pentagons. Now we can show that Theorem 2.1 actually does imply Theorem 1.1: Proof of Theorem 1.1, assuming Theorem 2.1: The proof is by induction on the number of vertices of G. Let G be a triangle-free planar graph of maximum degree three. We may assume that G is connected; otherwise, consider each component of G in turn. First consider the case where G has no subgraph isomorphic to a forbidden graph. If G is a difficult component, then λ(G) = 1, so Theorem 2.1 implies that G has an independent set with size at least   5 3 1 1 3 1 3 ≥ n, n+ (3n − 2e) − ≥ n+ − 8 24 12 8 24 12 8 since every difficult component has at least five vertices of degree two, by Lemma 3.2. If G is not difficult, 1 (3n − 2e) ≥ 83 n. then by Theorem 2.1, G has an independent set with size at least 38 n + 24 Now suppose that G has a subgraph L which is a link graph or is Kayak. Suppose the former is the case. Let v1 , . . . , v4 be the linking vertices of L. If vi has degree two in G for some i, let I be a big set of 7 L, such that vi is the only linking vertex of L in I; such a set exists by Lemma 3.3(iv). Deleting V (L) and applying induction, we obtain an independent set I ′ . Then I ∪ I ′ is an independent set of G with size at least 83 V (G) , as desired. So suppose that vi has degree three in G for all i. Let ui be the neighbor of vi not in V (L) for all i, and without of loss of generality, suppose that v1 is not adjacent to v2 . Delete V (L) and add an edge u1 u2 to obtain the graph G′ . This edge is a cut-edge by Lemma 3.3(v), so G′ is triangle-free. Furthermore, G′ has maximum degree at most three and is planar. We apply induction to G′ to obtain an independent set I ′ and add an independent set I of L such that the only linking vertex of L in I is v1 (or v2 , depending on whether u1 or u2 is in the independent set of G′ ). Then I ∪ I ′ is an independent set as desired. This concludes the case where L is a link graph. The proof of the case where L is isomorphic to Kayak is similar and easier, as no cut-edge needs to be added, and is omitted. 4. Preliminaries Lemma 4.1. The graph G is connected, and G is not difficult. Proof : If G is not connected, then one of its components is a smaller counterexample. If G is a difficult graph, then it has e = 32 n − 23 b(G) − 1 edges by Lemma 3.2 and an independent set with size at least 1 1 e − 12 , so G satisfies Theorem 2.1, a α0 = 38 n + 18 b(G). But a simple calculation shows that α0 = 21 n − 12 contradiction. We now state a general-purpose induction lemma. Lemma 4.2. Let G′ be obtained from G by deleting a set X of vertices and (possibly) adding edges, and suppose that G′ is valid. Furthermore, suppose that every independent set of G′ can be extended to one of G by adding at least A vertices. Then λ(G′ ) > 12A − 6N + E, where N = X and E = E(G) − E(G′ ) . Proof : Since G is a minimal counterexample, G′ satisfies Theorem 2.1; hence G has an independent set with size at least A+ 1 1 1 1 1 1 n(G′ ) − e(G′ ) − λ(G′ ) = A + (n − N ) − (e − E) − λ(G′ ) 2 12 12 2 12 12  
1 1 1 n− e + 12A − λ(G′ ) − 6N + E . = 2 12 12 We must have 12A − λ(G′ ) − 6N + E < 0; otherwise, G would not be a counterexample to Theorem 2.1. This paper will make extensive use of the notation introduced in Lemma 4.2. In the simplest case, if I is an independent set of a graph, we will let X = I ∪ N (I). Then we will delete the set X and implicitly use Lemma 4.2 to get an immediate lower bound for λ(G′ ); clearly the smaller graph must also be valid. The next two lemmas will establish an upper bound on λ(G′ ). Lemma 4.3. Suppose that D is a difficult block that is an induced subgraph of G. Then δ(D) ≥ 3. Proof : Let G and D be as stated, X = V (D), k = X , and suppose for a contradiction that δ(X) ≤ 2. Let G′ = G\X; then by Lemma 3.1(v) every independent set in G′ can be extended to one in G by adding at least A = 38 k + 81 vertices, and E = 32 k − 25 + δ(X) by Lemma 3.1(i). By Lemma 4.2 the graph G′ has δ(X) components, and each is a difficult graph. Thus G is difficult, contrary to Lemma 4.1. Recall that if D is a difficult graph, then b(D) denotes the number of difficult blocks of D; that is, the number of blocks that have at least three vertices. Lemma 4.4. Suppose that D is a difficult graph that is an induced subgraph of G. Then δ(D) ≥ 2λ(D) + b(D) ≥ 3λ(D). 8 Proof : Let G and D be as stated and let B be the set of all difficult blocks B of D; then B = b(D). For B ∈ B we define val(B) to be the number of cut-edges of D with one end in V (B) (and hence precisely one end in V (B)), and we define ξ(B) to be the number of edges of G with one end in V (B) and the other in V (G) \ V (D). Then for every B ∈ B we have ξ(B) + val(B) = δ(B) , but δ(B) ≥ 3 by Lemma 4.3. By summing over all B ∈ B we obtain δ(D) + 2(b(D) − λ(D)) ≥ 3b(D), which gives the desired result. Now we present a variation of Lemma 4.2, in which the graph G′ contains a link graph or Kayak as a subgraph. Lemma 4.5. Let G′ be obtained from G by deleting a set X of vertices and adding edges, so that G′ is planar, triangle-free, and has maximum degree at most three. Let A, N and E be defined as in Lemma 4.2. Suppose L is a subgraph of G′ such that L is a link graph and G′ \ V (L) has no subgraph isomorphic to a link graph or Kayak. Let k be the number of linking vertices of L which have degree three in G′ . If k ≤ 3, let G′′ be G′ \ V (L); otherwise, suppose that G′′ is obtained from G′ by deleting V (L) and adding an edge between two vertices which are adjacent to two non-adjacent linking vertices of L. Then: (i) The graph G′′ is valid; (ii) If k ≤ 3, then λ(G′′ ) > 12A − 6N + E + k − 2; and (iii) If k = 4, then λ(G′′ ) > 12A − 6N + E + 1. Proof : We proceed as in the proof of Lemma 4.2, except that we delete Y = X ∪ V (L) and possibly add an edge. Let us assume that L has ℓ vertices. If k ≤ 3, then there is a linking vertex w of L which has degree two in G′ . We can find a big set of L which uses only w among the linking vertices of L, so we can extend an independent set
of G′′ by adding an independent set with size A + 83 ℓ; also we are deleting N + ℓ vertices and E + 32 ℓ − 2 + k edges. The graph G′′ is valid (being G \ Y ), so Lemma 4.2 implies that G′′ has more than       3 3 12 A + ℓ − 6(N + ℓ) + E + ℓ − 2 + k = 12A − 6N + E + (k − 2) 8 2 difficult components, which proves (ii). If k = 4, then the edge added to G′ \ V (L) is a cut-edge by Lemma 3.3(v). Since every forbidden graph is 2-connected, G′′ is valid (being G \ Y , with a cut-edge added), so we can apply Lemma 4.2 again. Doing the calculation as above proves (iii). Lemma 4.6. Let G′ be obtained from G by deleting a set X of vertices and adding edges, such that G′ is planar, triangle-free, and has maximum degree at most three. Let A, N and E be as defined in Lemma 4.2. Suppose K is a subgraph of G′ isomorphic to Kayak, such that G′ \ V (K) has no subgraph isomorphic to a link graph or Kayak. Let k = δG′ (K) , and let G′′ be G′ \ V (K). Then the graph G′′ is valid, and λ(G′′ ) > 12A − 6N + E + k − 1. Proof : This follows by an argument similar to and easier than that of Lemma 4.5, using the fact that Kayak has an independent set with size six disjoint from its vertices of degree two. Lemma 4.7. Let G′ be obtained from G by deleting a set X of vertices such that δ(X) ≤ 3, followed by adding an edge joining two vertices of G′ adjacent to X, so that G′ is planar, triangle-free, and has maximum degree at most three. Let A, N , and E be as in Lemma 4.2. Then 12A − 6N + E ≤ 1, and if equality holds, then G′ has a component that is a link graph. Proof : Suppose that 12A − 6N + E ≥ 1. We must now show that equality holds, and that G′ has the structure stated. Note that if λ(G′ ) ≥ 2, then G′ has a difficult component D not containing the added edge. This component D has δ(D) < 3 in G, contrary to Lemma 4.4; thus λ(G′ ) ≤ 1. Then Lemma 4.2 implies that G′ has a subgraph L isomorphic to a link graph or Kayak. Since G is valid, L includes the added edge, and hence G′ \ V (L) has no subgraph which is forbidden. Let k and G′′ be as in Lemma 4.5 or Lemma 4.6, accordingly. We have δG (G′′ ) ≤ δG (X) − 2 + k ≤ k + 1, because at least two edges in δ(X) have one end in V (L). Thus λ(G′′ ) ≤ 13 (k+1) by Lemma 4.4. If L is isomorphic to Kayak, then by Lemma 4.6, λ(G′′ ) ≥ k+1, which (along with our upper bound) implies that k ≤ −1; thus L is a link graph, and by Lemma 4.5, λ(G′′ ) ≥ 3 9 if k = 4, and λ(G′′ ) ≥ k if k ≤ 3. Again, our upper bound implies that 12A − 6N + E = 1 and k = 0, the latter of which is equivalent to L being a component of G′ . 5. Initial Reductions Lemma 5.1. G has minimum degree at least two. Proof : Let v be a vertex of degree at most one. If deg v = 0, G is the empty graph on one vertex, and the theorem holds. If v has degree one, let I = {v} and X = I ∪ N (I), whereupon λ(G \ X) > 12 − 6 · 2 + 1 = 1, by Lemma 4.2. But since δ(X) ≤ 2, λ(G \ X) = 0 by Lemma 4.4, a contradiction. Lemma 5.2. Let u and v be two adjacent vertices of degree two in G. Then u and v are in the vertex-set of some pentagon of G. Proof : Suppose that u and v are vertices of degree two which are adjacent. Let t and w be the other neighbors of u and v, respectively. Let G′ be the graph obtained from G by deleting the vertices X = {u, v} and adding the edge tw, with A = 1, E = 2, and N = 2. If G′ is triangle-free, then Lemma 4.7 implies that 2 = 12A − 6N + E ≤ 1, a contradiction. Thus G′ contains a triangle which uses the edge tw. The other two edges of this triangle, along with the edges tu, uv, and vw, form the desired pentagon in G. Lemma 5.3. In G, every vertex of degree two has exactly one neighbor of degree two. Proof : First, suppose there are three vertices u, v, w of degree two such that u and w are the neighbors of v. By Lemma 5.2, u and v lie on a pentagon, and this pentagon also includes w. But then the vertex-set P of this pentagon satisfies δ(P ) ≤ 2, contrary to Lemma 4.3. So now let v be a vertex of degree two, and suppose both its neighbors u and w have degree three. Let X = {u, v, w}, with A = 1, E = 6, N = 3, and δ(X) = 4, so that 34 ≥ λ(G \ X) > 0 by Lemma 4.2. Lemma 4.3implies that b(G \ X) ≤ 2 (since δ(X) has four edges). If b(G \ X) = 2, then let D1 and D2 be the difficult blocks of G \ X; then G is a sum of D1 and D2 . Since G is not a difficult block, by Lemma 4.3, we may assume that the vertices of D1 of degree two in G are non-adjacent. We then find a big set I1 of D1 so that these two vertices are the only two of degree two (in D1 ) in I1 ; this exists by Lemma 3.1(iv). Then we find a big set I2 of D2 avoiding the neighbors of u and w in D2 (two vertices); this exists by Lemma 3.1(v). 1 E(G) , and Then the set I = I1 ∪ I2 ∪ {u, w} is an independent set of G with size at least 21 V (G) − 12 so G satisfies Theorem 2.1, a contradiction. So the difficult component of G′ is a single block D. If all four edges in δ(X) are incident with D, then contracting the edges uv and vw shows that D is 4-accessible. By Lemma 3.1, D is either a pentagon or the graph G4 . If D is a pentagon, then G is nonplanar or has a triangle, and if D is the graph G4 , then G is isomorphic to Kayak, a forbidden graph. Thus by Lemma 4.3, exactly three edges in δ(X) are incident with D; the fourth (incident with w, without loss of generality) is incident with a non-difficult component of G \ X. Let L be the subgraph of G induced by the set V (D) ∪ {u, v, w}. Since G is valid, L is not a 3-augmentation of the difficult block D; hence the vertices in D which have degree two in G are non-adjacent. We now let J be the union of a big set of D using only these two vertices among the vertices of degree two in D and {u, w}. Then let Y = J ∪ N (J); Lemma 4.2 then implies that    1 1 (3d + 1) + 2 − 6(d + 4) + (3d − 5) + 8 8 2    3 3 5 d+ −6+ + 24 − 24 − + 8 = 7, 2 2 2  λ(G \ Y ) > 12  9 = 2 where d = V (D) . However, this contradicts Lemma 4.4, because δ(Y ) ≤ 2. Before proceeding, it is worth pointing out the fact that the terms involving d in the proof of Lemma 5.3 cancelled is not coincidental; in the proofs of other lemmas, similar terms will cancel as well. 10 6. The Girth of G is At Least Five Lemma 6.1. Let D be a difficult graph, and let Y ⊆ V (D) be a set of vertices of degree two with size at most four such that Y ∩ V (B) ≤ 2 for every block B of D, and if equality holds for two distinct non-trivial blocks B1 and B2 of D, then B1 and B2 are not adjacent in D. Then D has a big set disjoint from Y . Proof : We proceed by induction on b = b(D). If D has only one block, then the statement follows from Lemma 3.1(v). We may assume that D is connected, for otherwise the statement follows by induction. The assumptions imply that there exists an end-block B of D with Y ∩ V (B) ≤ 2. Let v be the unique vertex of B that is incident with a cut-edge of D, and let u be the other end of the cut-edge incident with v. If Y ∩ V (B) ≤ 1, then by Lemma 3.1(v) the graph B has an independent set I0 disjoint from Y ∪ {v} the graph D\V (B) has an independent set I1 disjoint from with size at least 83 V(B) + 18 ; by induction  Y with size at least 3 8 V (D) − V (B) + 81 (b − 1), and I0 ∪ I1 is as desired. Thus we may assume that Y ∩ V(B) = 2. Then  we choose I0 disjoint from Y (but possibly containing v), and choose I1 disjoint from Y ′ = V (D) − V (B) ∩ (Y ∪ {u}) by the induction hypothesis. Such a choice is possible, because Y ′ ≤ 3. Again, I0 ∪ I1 is as desired. Lemma 6.2. Let v1 v2 v3 v4 v1 be a 4-cycle in G. Then v1 , v2 , v3 , and v4 have degree three. Proof : Suppose v1 v2 v3 v4 v1 is a 4-cycle in G. If deg v1 = 2, then by Lemma 5.3, one of the neighbors of v1 also has degree two; by symmetry, we may assume that deg v2 = 2. Then, by Lemma 5.2, v1 and v2 lie on a pentagon; thus v3 and v4 must have a common neighbor, and this neighbor along with v3 and v4 forms a triangle in G. Lemma 6.3. G has no 4-cycles. Proof : Suppose v1 v2 v3 v4 v1 is a 4-cycle which appears in G. By Lemma 6.2, all of v1 , v2 , v3 , v4 have degree three. Let vi+4 be the third neighbor of vi , for i = 1 to 4. If v5 = v7 , then let I = {v1 , v3 }, so that X = {v1 , v2 , v3 , v4 , v5 }. Then deg v5 = 3 by Lemma 6.2, and so A = 2, E = 9, N = 5, and δ(X) = 3, and thus 33 ≥ λ(G \ X) > 8 · 2 − 4 · 5 + 9 = 5, by Lemma 4.4 and Lemma 4.2, a contradiction. Thus v1 ,. . . ,v8 are pairwise distinct (as G is triangle-free). Assume for a moment that v5 has degree two. Then by Lemma 5.3 it has a neighbor v of degree two, and by Lemma 5.2 the edge v5 v belongs to a pentagon C0 . By Lemma 4.3 the other three vertices of C0 have degree three. There are three possibilities: either v = v7 , or v is adjacent to v6 , or v is adjacent to v8 . Thus we have shown: (1) If v5 has degree two, then either v6 or v8 has degree three, or v7 has degree two, as well as analogous statements for v6 , v7 , and v8 . Since G has no subgraph isomorphic to Λ0 (see Figure 7), either v5 is not adjacent to v7 , or v6 is not adjacent to v8 . From the symmetry we may assume the former. We claim that both v5 and v7 have degree three. To prove this claim suppose for a contradiction that v5 has degree two. Let v be the neighbor of v5 of degree two and C0 a pentagon containing the edge vv5 ; since v 6= v7 we may assume that v is adjacent to v6 , and hence v6 has degree three. If v8 has degree two, then by the statement analogous to (1) applied to v8 in place of v5 we deduce that v7 has degree three. Thus one of v7 and v8 has degree three. If v7 has degree three let I0 = {v, v1 , v3 }; otherwise let I0 = {v, v2 , v4 }. Let X consist of I0 and all its neighbors, let G1 = G \ X, and let E = E(G) − E(G1 ) . It follows that E ≥ 13. (This is a bit tricky to see when v7 has degree two and v6 is adjacent to v8 . But then v7 has a neighbor u of degree two by Lemma 5.3 and the edge uv7 belongs to the edge-set of a pentagon by Lemma 5.2, and hence u is adjacent to v8 . It follows that G is isomorphic to the graph G∗ in Figure 8, but this graph satisfies Theorem 2.1, a contradiction.) From Lemma 4.2 we deduce that λ(G\X) ≥ 12·3−6·8+13+1 = 2, contrary to Lemma 4.3, because δ(X) ≤ 4. This proves our claim that both v5 and v7 have degree three. 11 ❏ Figure 8. The Graph G∗ Now let I = {v1 , v3 }, X = {v1 , v2 , v3 , v4 , v5 , v7 }, and G′ = G\X. Lemma 4.2 then implies that λ(G ) ≥ 12 · 2 − 6 · 6 + 12 + 1 = 1. Let I1 = {v2 , v4 , v5 } and I2 = {v2 , v4 , v7 }, and for i = 1, 2 let Yi be the set of all neighbors of Ii in V (G′ ). Thus Y1 and Y2 are at most four, and Y1 ∩Y2 = 2. We claim the following. ′ (2) For i = 1, 2, and for every difficult block B of G′ , Yi − {v6 } 6⊆ V (B) and Yi − {v8 } 6⊆ V (B). To prove (2) it suffices to show, by symmetry, that Y1 − {v8 } 6⊆ V (B). Suppose for a contradiction that Y1 − {v8 } ⊆ V (B) for some difficult block B of G′ . Assume for the moment that the component of G containing B is difficult. Let u, v be such that Y1 − {v8 } = {u, v, v6 }. By Lemma 3.1(i) the set V (B) − {u, v, v6 } includes precisely two vertices x and y that have degree two in B. Since the subgraph of G induced by V (B) ∪ {v1 , v2 , v5 } is not a 3-augmentation of B (as it would be a link graph which would be a subgraph of G), we deduce that x, y are not adjacent. By Lemma 5.3, both x and y have degree three in G, and so each of them is adjacent to v4 , v7 or to a vertex of a component C of G′ \ V (B). If one of x, y is adjacent to a vertex of C, then C has a vertex adjacent to v4 or v7 by Lemma 4.4. In any case, we conclude (by contracting the edges v1 v2 , v2 v3 , v1 v4 , v3 v7 , v4 v8 , and the edges of E(C) if C exists) that B has a planar drawing with all five vertices of degree two incident with the same region. By Lemma 3.1(vi) B is a pentagon. But the neighbors of v5 are consecutive on the pentagon by planarity, contrary to the fact that G is triangle-free. If the component of G containing B is not difficult, then consider a difficult component D of G′ ; D exists because λ(G′ ) ≥ 1. Since δ(X) = 6, Y2 − {v6 } ⊂ V (D); also, δ(D) = 3, so D is a difficult block. Proceeding as above, we obtain a similar contradiction for D. This proves (2). (3) For i = 1, 2, and for every difficult block B of G′ , Yi ∩ V (B) ≤ 2. It suffices to prove (3) for i = 1. By (2) and symmetry it suffices to rule out the possibility that {v6 , v8 , v} ⊆ V (B), where v is a neighbor of v5 other than v1 . So suppose for a contradiction that this is the case. Since G is planar, no difficult block of G′ other than B contains both a neighbor of v5 and a neighbor of v7 . From Lemma 4.3, we deduce that if G′ has a difficult block other than B in a difficult component, then it has exactly one such block B ′ , and B ′ is adjacent to B and contains two neighbors of v7 . Thus δ(B) ≥ 4, and hence δ(B) = 5 by Lemma 3.1(i) and Lemma 5.3. Thus Y1 ⊆ V (B), contrary to (2). Thus B is the only difficult block of G′ (and hence B = G′ ). If V (B) includes a neighbor of v7 , then again δ(B) = 5, and V (B) includes either both neighbors of v5 , or both neighbors of v7 , but either case contradicts (2). Thus V (B) includes no neighbor of v7 . By Lemma 3.1(v) there exists an independent set I ′ in B disjoint from {v6 , v8 } with size at least 18 (3d + 1), where d = V (B) . Let X = V (B) ∪ {v1 , v2 , v3 , v4 , v5 }; then every independent set of G\X can be enlarged to one in G by adding I ∪ {v2 , v4 }. By Lemma 4.2 we see that G\X has at least 12     3 1 5 3 d + + 2 − 6(d + 5) + d − + 10 + 1 = 4 8 8 2 2 difficult components, contrary to Lemma 4.4. This proves (3). 12 (4) For i = 1, 2, there exist adjacent difficult blocks B, B ′ of G′ such that Yi ∩ V (B) = Yi ∩ V (B ′ ) = 2. To prove (4) suppose for a contradiction that the statement is false, and choose an integer i ∈ {1, 2} such that (i) Condition (4) does not hold for i; and (ii) Subject to (i), the number of vertices of Yi that belong to difficult blocks of G′ is maximum. We claim that Yi has at least two vertices in difficult blocks of G′ . Indeed, otherwise not both elements of Y1 ∩ Y2 belong to difficult blocks of G′ , and hence 3 − i satisfies (i). But δ(D) ≥ 3 for every difficult component D of G′ by Lemma 4.4, and hence Y3−i has at least two vertices in difficult blocks of G′ , contrary to (ii). This proves our claim that Yi has at least two vertices in difficult blocks of G′ . We may assume that i = 1. Let D be the union of the difficult components of G′ , and let d = V (D) . By Lemma 6.1, there exists an independent set I in D with size at least 83 d + 18 b(D) such that I ∩ Y1 = ∅. If we now let X ′ = V (D) ∪ {v1 , v2 , v3 , v4 , v5 } ∪ Y1 ; then X ′ ≤ d + 7, because Y1 ∩ V (D) ≥ 2 by the above claim. Then every independent set in G\X ′ can be extended to one in G by adding I ∪ I1 , and so Lemma 4.2 implies that λ(G \ X ′ ) > 12    1 3 3 d + b(D) + 3 − 6(d + 7) + d − b(D) − λ(D) + 12 = 6 − λ(D) ≥ 4, 8 8 2 since λ(D) ≤ 2. Lemma 4.4 implies that G \ X ′ has no difficult components. This contradiction proves (4). Now let B1 and B2 be the difficult blocks as in (4) for i = 1, and let B3 and B4 be the difficult blocks for i = 2. Then one of B1 , B2 equals one of B3 , B4 , so we may assume that B1 = B4 . Then B2 = B3 or B2 6= B3 ; in either case B1 , B2 , and B3 are the only difficult blocks of G′ , and there are exactly six edges between X and V (B1 ) ∪ V (B2 ) ∪ V (B3 ). Thus V (G′ ) = V (B1 ) ∪ V (B2 ) ∪ V (B3 ). If B2 6= B3 , then there is exactly one edge between V (B1 ) and V (B2 ), exactly one edge between V (B1 ) and V (B3 ), and none between V (B2 ) and V (B3 ). Thus Lemma 3.1(i) implies that V (G′ ) contains a vertex of G of degree two with both neighbors of degree three, contrary to Lemma 5.3. If B2 = B3 , then there is exactly one edge between V (B1 ) and V (B2 ). Thus there are exactly four edges between X and V (Bi ) and two between X and V (B3−i ), for i = 1 or 2; otherwise, a vertex violating Lemma 5.3 is found as in the previous case. This, however, contradicts (3) or makes G nonplanar. Hence, G cannot have a 4-cycle after all. 7. G is 3-Regular Lemma 7.1. G is 3-regular. Proof : By Lemma 5.1, G has minimum degree at least two. Suppose for a contradiction that v1 is a vertex of degree two. By Lemma 5.3, v1 has a neighbor of degree two, which will be called v2 . By Lemma 5.2, v1 and v2 lie on a pentagon; i.e., there exist vertices v3 , v4 , v5 , such that v1 v2 v3 v4 v5 v1 is a pentagon. We may assume that the vertices {v1 , . . . , v5 } are chosen to minimize the number of components of G \ {v1 , . . . , v5 } among all choices of {v1 , . . . , v5 }. If any of the vertices v3 , v4 , v5 has degree two, then Lemma 4.3 (with V (D) = {v1 , v2 , v3 , v4 , v5 }) is violated, so these vertices all have degree three. Let v6 , v7 and v8 be the third neighbors of v3 , v4 , and v5 , in that order; the vertices v1 ,. . . ,v8 are pairwise distinct by Lemma 6.3. We now claim the following: (1) Any two vertices among v6 , v7 , and v8 have a common neighbor. We shall prove (1) for the pair v6 and v8 ; the proof for the other pairs is analogous. So suppose for a contradiction that v6 and v8 have no common neighbor, and let G1 be obtained from G by deleting the vertices v1 ,. . . ,v5 and adding the edge v6 v8 . Then G1 is planar, triangle-free, and has maximum degree three. Using the notation of Lemma 4.2, we have 12A − 6N + E = 12 · 2 − 6 · 5 + 7 = 1, and so by Lemma 4.7, G1 has a component L which is a link graph. If L is not all of G1 , then G \ {v1 , . . . , v5 } is disconnected, and it is possible to choose a different 5-tuple v1′ , . . . , v5′ of vertices of L in such a way that G \ {v1′ , . . . , v5′ } is connected. Thus, G1 is a link graph. Note that every vertex in G1 except for v7 has the same degree in G, 13 due to the way we constructed G1 . But the linking vertex v of G1 adjacent to v7 in G1 has degree two in G, and both of its neighbors have degree three, contradicting Lemma 5.3. This proves (1). Let v9 be the common neighbor of v6 and v8 , v10 the common neighbor of v6 and v7 , and v11 the common neighbor of v7 and v8 . (2) The vertices v9 , v10 , and v11 are pairwise distinct. To prove (2), note that if any pair of these vertices are the same, then there is a vertex adjacent to v6 , v7 , and v8 . It is thus sufficient to show that v9 , v10 , and v11 are not all the same vertex. If this is the case, let u and v be the third neighbors of v6 and v7 , respectively. Now fix a planar embedding of G. By symmetry, we may assume that v lies on the opposite side of the cycle v9 v7 v4 v3 v6 v9 from v6 . Now let G′ be the graph obtained from G by deleting the vertices v1 ,. . . ,v7 ,v9 and adding the edge uv. No forbidden graphs are created, because uv is a cut-edge of G′ . Using the terminology of Lemma 4.2, N = 8, E = 12, and A = 3, because an independent set of G′ can be extended to one of G by adding the vertices v1 , v3 , and v7 , or the vertices v2 , v4 , and v6 . Lemma 4.2 implies that λ(G′ ) > 0, but we will show that G′ has no difficult components. The component of G′ containing v8 is not difficult, because v8 has degree one in G′ ; the component containing the edge uv is not difficult, because G would have a difficult block D with δ(D) ≤ 2, violating Lemma 4.3. This proves (2). Now, the vertices v9 , v10 , and v11 cannot have degree two, because their neighbors would both have degree three, violating Lemma 5.3. Let v12 , v13 , and v14 be the third neighbors of v9 , v10 , and v11 , respectively. These three vertices are pairwise distinct; otherwise G would violate Lemma 6.3; and none of these vertices can equal any of v1 ,. . . ,v11 , because a degree condition would be violated. Hence v1 ,. . . ,v14 are distinct vertices. We then claim the following: (3) The vertex v12 is adjacent to v13 and v14 . By symmetry, it suffices to prove that v12 and v13 are adjacent. To prove this, suppose for a contradiction that v12 is not adjacent to v13 . Let G′ be the graph obtained from G by deleting the vertices {v1 , v2 , v3 , v4 , v5 , v6 , v8 , v9 } and adding the edge v10 v12 . Note that if no forbidden graphs are created, we have A = 3, E = 12, and N = 8, and so λ(G′ ) > 0, by Lemma 4.2. Since G′ is connected, either λ(G′ ) = 1 or G′ contains a forbidden subgraph. Assume first that λ(G′ ) = 1. We shall show that G′ is a difficult block, whereupon G is obtained from ′ G by an 8-augmentation, a contradiction to Lemma 4.1, because then we would have λ(G) = 1. First of all, v10 v12 cannot be a cut-edge of G′ : then the component of G′ \ v10 v12 containing v12 would be a difficult subgraph of G contradicting Lemma 4.3. So v10 v12 lies in some difficult block B. If v7 v11 is a cut-edge, then the component of G′ \ v7 v11 containing v7 must be a difficult block, but this cannot be, as v7 would have at most one neighbor. Thus v7 v11 lies in a (difficult) block. Now v7 v10 can not be a cut-edge, either, by the same argument (as v11 would then have degree one). Thus, the vertices v7 , v10 , v11 , v12 , and v14 all lie in B. But again, if B is not all of G′ , then any component of G′ \ V (B) contradicts Lemma 4.3. So G′ must be a difficult block, and λ(G) = 1, contrary to Lemma 4.1. This completes the case when λ(G′ ) = 1. Next suppose G′ has a subgraph K isomorphic to Kayak. We will then show that we can do better than Lemma 4.6. First of all, v7 is not in V (K); if so, then (since it has degree two in G′ ) v11 is as well, and consequently, K contains two adjacent vertices of degree two, which is not true for Kayak. Similarly, v11 is not in V (K), either. Now we will delete the vertices Y = V (K) ∪ {v1 , . . . , v11 } from G; here we have A = 4 + 6 = 10, N = 10 + 16 = 26, and E ≥ 12 + 23 + 2 = 37. Since there are at most two edges in δ(Y ), λ(G \ Y ) = 0. (Note that the edge v7 v10 is incident with Kayak, and is thus not incident with any difficult components of G \ Y .) Now Lemma 4.2 implies that 0 = λ(G \ Y ) > 12 · 10 − 6 · 26 + 37 = 1, a contradiction, implying that Kayak is not a subgraph of G′ . Suppose finally that a link graph L (with ℓ vertices) is a subgraph of G′ . It contains the edge v10 v12 , as G is valid. Again, we want to show that an 8-augmentation applied to L produces a graph which is a subgraph of G. For the 8-augmentation construction to be satisfied, the edge v7 v11 (or equivalently, v7 v10 ) must be an edge of L. Suppose not; then v10 v13 is an edge of L, and v10 has degree two in L and so is a linking vertex of L. Moreover, since v7 and v11 have degree two in G′ (and are not adjacent to v10 ), they cannot be linking vertices of L, because Lemma 3.3(v) would be violated. Thus v7 , v11 6∈ V (L). 14 Now let w, x, y, and z be the linking vertices of L, with (by Lemma 3.3(ii)) wx and yz being edges of L. Note that we may assume that v10 = w, which makes x one of v12 or v13 . Now we will want to delete the set Y = V (D) ∪ {v1 , . . . , v9 , v11 } and possibly add a cut-edge to produce a graph G′′ . If one of the vertices x, y, z has degree two in G, then we do not add any cut-edges. Our independent set I ′ will be the union of {v1 , v6 , v7 , v8 } and a big set of L avoiding the vertices w and two vertices among x, y, z such that the third has degree two; also let Y = I ′ ∪N (I ′ ). Then we have A = 4+ 83 ℓ, E ≥ 14+ 32 ℓ−2+1 (the extra 1 is because v7 v10 is being deleted), N = 10 + ℓ, and δ(Y ) ≤ 3, so Lemma 4.2 and Lemma 4.4 imply that 33 ≥ λ(G \ Y ) > 1, a contradiction. If all of x, y, and z have degree three, we add a cut-edge joining two components of G\Y (which exist by Lemma 3.3, parts (iv) and (v)) and obtain A = 4+ 83 ℓ, E = 14+ 23 ℓ−2+3, and N = 10+ℓ; we also know that λ(G\Y ) ≤ 1; otherwise G has a subgraph D which is difficult and for which δ(D) ≤ 2. But this computation implies that 1 ≥ λ(G \ Y ) > 3, another contradiction. This proves (3). Now, v13 and v14 have degree three (again, because two of their neighbors have degree three); letting v15 and v16 be the third neighbors of v13 and v14 (respectively), it follows that the vertices v1 ,. . . ,v16 are pairwise distinct by Lemma 6.3. Now, v15 v16 is not an edge of G, as then Λ1 (see Figure 7) would be a subgraph of G. From Lemma 5.3 and Lemma 5.2 we deduce that v15 and v16 both have degree three. Now, we let I = {v3 , v5 , v7 , v9 , v13 , v14 } (and X = I ∪ N (I)), with A = 6, E = 24, N = 16, and δ(X) = 4, 34 ≥ λ(G \ X) > 1 by Lemma 4.2 and Lemma 4.4, which cannot be satisfied by any integer. 8. G is 3-Connected Before it is shown that G is 3-connected, it should be pointed out that so far we have not used the fact that α(G) is an integer. We will do so now, and we will obtain stronger results than are obtained by Lemma 4.2. For instance, if n is even and not divisible by eight, then the two statements α(G) ≥ 3 n 8 and α(G) ≥ 3 1 n+ 8 4 are equivalent. Another fact we will use is that the parity of V (H) is the same as the parity of its deficiency; that is, they are both even or both odd. Also, the deficiency of an induced subgraph H of G is the number of edges with exactly one end in V (H), since G is 3-regular. Lemma 8.1. The graph G is 2-connected. Proof : To show that G is 2-connected, suppose for a contradiction that G has a cut-vertex v. Let J be a component of G\v that includes at most one neighbor of v, and let G1 be obtained from J by deleting that neighbor. Let G2 be obtained from G\V (G1 ) by deleting v and all its neighbors. The graph G1 has a deficiency of 2, and G2 has a deficiency of 4. Let Gi have ni vertices, for i = 1, 2. Since G1 has a deficiency of 2, n1 is even; n2 is even as well, being n − n1 − 4. Neither of Gi has any difficult components, not having enough vertices of degree 2. Taking the union of independent sets of each Gi and {v}, we see that α(G) ≥         3 3 3 3 2 4 1 1 3 3 3 + +1≥ + + 1 = (n − 4) + = n, n1 + n2 + n1 + n2 + 8 24 8 24 8 4 8 4 8 2 8 contrary to the assumption that G is a counterexample to Theorem 2.1. The inequalities involving the ceiling function hold because n1 and n2 are both even. This proves that G is 2-connected. Lemma 8.2. If G has a vertex cut {u, v}, then u and v are nonadjacent. Proof : Suppose for a contradiction that G has a vertex cut {u, v} such that u and v are adjacent. Let G′1 and G′2 be the components of G \ {u, v}; there are exactly two, because G is 2-connected. Let G1 be the subgraph of G induced by V (G′1 ) ∪ {u, v}, V (G1 ) . The graph G1 has a deficiency of 2, no n1 =  3 and let 2 3 difficult components, and thus α(G1 ) ≥ 8 n1 + 24 ≥ 8 n1 + 14 (n1 is even). 15 By symmetry, we may assume that u is not in an independent set I1 of G1 of this size. If we let G2 be G′2 with the neighbor of v in G′2 removed, then G2 has a deficiency of 3, no difficult components, and thus 3 , where n2 = V (G2 ) . Then I1 ∪ I2 is an independent set of an independent set I2 of size at least 83 n2 + 24 G with size at least     3 3 3 1 1 3 3 3 3 + = (n1 + n2 ) + = (n − 1) + = n. n1 + n2 + 8 4 8 8 8 8 8 8 8 This proves the lemma. To handle the case where G has a vertex cut of size two, we will want to add an edge between the two vertices in that vertex cut. The problem is that forbidden graphs might be created. The following lemma shows that, under the right conditions, the only forbidden graphs that can be created are triangles. Lemma 8.3. Let u, v ∈ V (G) be nonadjacent, P an induced u-v path in G, H an induced subgraph of G \ {u, v} that includes all the internal vertices of P , and assume that there exists a component J of the graph H \ V (P ) such that (∗) every vertex of H with a neighbor in V (G) − V (H) − {u, v} belongs to J. Let G′ be obtained from G\V (H) by adding an edge with ends u and v. Then G′ has no subgraph isomorphic to a link graph or Kayak. Proof : We prove the lemma for a link graph; the proof for Kayak is almost identical. Suppose for a contradiction that L′ is a link graph that is a subgraph of G′ . Then u, v ∈ V (L′ ), and they are adjacent in L′ , for otherwise L′ would be a subgraph of G. Let L = (L′ ∪P )\uv. Then L is a subgraph of G, and it is obtained from a link graph by subdividing one edge. Let us fix a planar embedding of G; that induces a planar embedding of L. The graph L′ has two pairs of adjacent vertices of degree two, and no face of L′ is incident with all four degree two vertices. Thus we may choose a pair x, y of adjacent vertices of degree two of L′ such that as vertices of L they are not incident with the face of L that includes the connected graph J. Thus, in particular, x, y 6∈ V (P ). But the graph G is cubic by Lemma 7.1, and hence x has a neighbor x′ that is not a neighbor of x in L. Then x′ 6∈ {u, v}, because u and v have degree three in L. By (∗), x′ does not belong to P , and hence there exists a component K of G \ V (L) with a neighbor of x. By Lemma 8.2, K has a neighbor z in L \ {x, y}. But z cannot be a vertex of L′ of degree two, for x, y, z are then incident with the same face of L. Thus z is an internal vertex of P . Now let Q be a path with ends z and x and interior in K. Since z ∈ V (H) and x 6∈ V (H) ∪ {u, v}, the path Q has two adjacent vertices a, b such that a ∈ V (H) and b 6∈ V (H) ∪ {u, v}. Thus a ∈ V (J) by (∗). But that contradicts our choice of x and y: We have just shown that x and y are incident with the face of L that contains J. Now we can finish the proof of 3-connectedness: Lemma 8.4. Proof : The graph G is 3-connected. We first show that the following claim holds: (∗) If G has a vertex cut {u, v}, where u and v have no common neighbor, then each component of G\{u, v} contains two neighbors of either u or v. Suppose for a contradiction that G\{u, v} has a component, say G′1 , containing exactly one neighbor of each of u and v, and let G′2 be obtained from G by deleting V (G′1 ) and u and v. Let Gi be the subgraph of G induced by V (G′i ) ∪ {u, v}, with the edge uv added. This graph G1 is triangle free, because u and v have no common neighbor, by assumption. We need to show that G1 does not contain Kayak or a link graph. To do so, note that we can use Lemma 8.3, where H is G′2 , and P is an induced u-v path, all of whose internal vertices are in V (G′2 ). No vertex of H has a neighbor in V (G′1 ) = V (G) − V (H) − {u, v}, since {u, v} is a vertex cut. Hence, condition (∗) in Lemma 8.3 is satisfied vacuuously. It then follows that G1 does not contain a link graph or Kayak; i.e., G1 is a valid graph. Let n1 = V (G1 ) , and let us assume first that n1 6≡ 2 (mod 8). The graph G1 has a deficiency of 2, and 2 ≥ 83 n1 + 12 , as n1 hence it is not difficult; thus it contains an independent set I1 of size at least 83 n1 + 24 16 is even and n1 6≡ 2 (mod 8). Since uv is an edge of G1 , u and v cannot both be in I1 ; hence we may assume, by symmetry, that v is not in I1 . Let G′′2 be G′2 with the neighbors of u deleted; then G′′2 has deficiency 6. This graph has no difficult components; if it did, then that component would have to be a pentagon because it is a 5-accessible difficult subgraph of the 3-regular graph G, and some neighbor of u in G′′2 would then have to be adjacent to two vertices in this pentagon, forming a cycle of length four. This does not happen, because of Lemma 6.3, so G′′2 has no difficult components, and so it has an independent set I2 with size at 6 , where n′′2 = V (G′′2 ) . Thus least 83 n′′2 + 24 3 n > α(G) ≥ 8  1 3 n1 + 8 2  +  3 ′′ 1 n + 8 2 4  = 3 3 3 3 3 (n1 + n′′2 ) + = (n − 2) + = n, 8 4 8 4 8 a contradiction. Hence n1 ≡ 2 (mod 8). Now consider G2 , which does not contain a link graph or Kayak as a subgraph (by the same argument as for G1 ); it is triangle-free because u and v were assumed to have no common neighbor. It also has a deficiency of zero, and thus an independent set I2′ with size at least 83 n2 . Again, not both u and v are in I2′ , so we assume that u 6∈ I2′ and let G′′1 be G′1 with the neighbor of u (in G′1 ) deleted; it has n′′1 = n1 − 1 ≡ 1 (mod 8) 3 vertices. Then G′′1 has deficiency 3, and also an independent set with size at least 38 n′′1 + 24 ≥ 38 n′′1 + 83 . The union of these independent sets provides an independent set which contradicts the assumption that G is a counterexample to Theorem 2.1. This proves (∗). We are now ready to prove the lemma itself.We will use Lemma 8.2 and Lemma 8.1 without further reference. Choose u and v so that {u, v} is a vertex cut of G, and suppose G′1 and G′2 are the components of G \ {u, v}. First, we may assume that each of G′1 and G′2 has two neighbors of u or two neighbors of v, because if G′1 only contains one neighbor u′ of u and only one neighbor v ′ of v, then we can use {u′ , v} instead of {u, v} in the analysis which follows. For definiteness, suppose u′ is now the only neighbor of u in G′1 , and that v ′ is the only neighbor of v in ′ G2 . Note that we have two more vertex cuts of size two in G: namely, C1 = {u′ , v} and C2 = {v ′ , u}. Both of these vertex cuts have the property that some component of G \ Ci only contains one neighbor of each vertex in Ci . Hence, by (∗), the vertices in Ci have a common neighbor, for both values of i. Let w be the common neighbor of u and v ′ , and let w′ be the common neighbor of u′ and v; note that these six vertices form a hexagon in G, because of Lemma 8.1. Now, let I = {u, v ′ , w′ } and let Gi be the subgraph of G′i induced by G′i \(I ∪N (I)). 6.3,  Then 4by Lemma G1 has a deficiency of 4, and consequently an independent set I1 with size at least 38 n′1 + 24 ≥ 38 n′1 + 41 , where n′1 = V (G1 ) , because n′1 is even. The graph G2 has a deficiency of 3 or 5 (note that the neighbor of u in G′2 other than w may be adjacent to a neighbor of v ′ ) and no difficult components, and so has an 3 , where n′2 = V (G2 ) . Then α(G) ≥ I ∪ I1 ∪ I2 ≥ 83 n, since independent set I2 with size at least 38 n′2 + 24 ′ ′ n1 + n2 = n − 9. This contradiction proves the lemma. Note that Lemma 8.4 has the following consequence: Lemma 8.5. Every pentagon of G is facial. Proof : If a pentagon is not facial, then its vertex-set divides the graph into at least two components, one of which has at most two neighbors in the vertex-set of the pentagon, contrary to Lemma 8.4. 9. Conclusion of the Proof of Theorem 2.1 There is one final lemma which is needed before we can finish off the proof of Theorem 2.1: Lemma 9.1. Let P = v1 v2 v3 v4 v5 v1 be a (facial) pentagon of G. Then the face adjacent to P and incident with the edge v1 v2 is also a pentagon. Proof : Let vi+5 be the neighbor of vi not in {v1 , v2 , . . . , v5 }, for i = 1, . . . 5, let X = {v1 , v2 , v3 , v4 , v5 , v9 }, and let G′ be obtained from G\X by adding the edge v6 v7 . We now need to show that G′ contains a triangle. 17 The graph G′ has a deficiency of 4, and so if it contained no forbidden graphs, we would have 4 ≥ 83 (n − 6) + 14 , since n = V (G) is even, and since we can extend an indeα(G ) ≥ 38 (n − 6) + 24 ′ pendent set of G to one of G by adding {v1 , v4 } or {v2 , v4 }, ′ α(G) ≥  3 1 (n − 6) + 8 4  +2= 3 n. 8 This shows that G′ must contain a forbidden graph. To see that the forbidden graph is a triangle, we will use Lemma 8.3, where P is the path v6 v1 v2 v7 , J = {v3 , v4 , v5 , v9 }, and H the subgraph of G induced by {v1 , v2 } ∪ J. The condition (∗) holds, because any vertex in V (H) adjacent to a vertex not in H must be v3 , v5 , v6 , or v7 . The forbidden graph cannot be a link graph or Kayak, so it must be a triangle; hence there is a vertex w adjacent to v6 and v7 . The cycle v6 v1 v2 v7 wv6 is a pentagon, so by Lemma 8.5, it is facial. This proves the lemma. Now, we can finally prove Theorem 2.1. The minimal counterexample G, by previous lemmas, must be 3regular and have girth at least five. An elementary application of Euler’s formula shows that G must then have a facial pentagon. (Its planar dual has a vertex with degree at most five.) The faces adjacent to this pentagon are also pentagons, by Lemma 9.1. We can also apply Lemma 9.1 to these facial pentagons to find out that all faces adjacent to these facial pentagons are pentagons. Consequently, every face is a pentagon, and so G must be isomorphic to a specific graph, the dodecahedron, which has 20 vertices and an independent set with size 8. However, G then satisfies Theorem 2.1, a contradiction. This finishes the proof of Theorem 2.1. 10. Acknowledgements The authors would like to thank Bojan Mohar for his work in an early stage of the proof, as well as Stephen Locke [private communication] who supplied two graphs (Λ1 and an 8-augmentation of Λ0 ) which turned out to be link graphs. We would further like to thank Dhruv Mubayi, Craig Tovey, and the referees, who provided useful suggestions. Special thanks to the referee who suggested that after Section 7 we prove that G is 3-connected. That resulted in a substantial simplification. 11. References [1] M. Albertson, B. Bollobás and S. Tucker, “The independence ratio and the maximum degree of a graph,” Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State University, Baton Rouge, La., 1976), pp. 43–50. Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976. [2] B. Bollobás, Graph theory. An introductory course. Graduate Texts in Mathematics, 63. SpringerVerlag, New York-Berlin, 1979. x+180 pp. [3] S. Fajtlowicz, “On The Size Of Independent Sets In Graphs,” Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic University, Boca Raton, Florida, 1978), pp. 269–274. Congressus Numerantium, No. XXI, Utilitas Math., Winnipeg, Man., 1978. [4] K. Fraughnaugh and S. Locke, “11/30 (Finding Large Independent Sets in Connected Triangle-Free 3-Regular Graphs),” Journal of Combinatorial Theory, Series B, 65 (1995), pp. 51–72. [5] H. Hatami, X. Zhu, “The fractional chromatic number of graphs of maximum degree at most three,” manuscript. [6] C. C. Heckman and R. Thomas, “A New Proof Of The Independence Ratio Of Triangle-Free Cubic Graphs,” Discrete Mathematics 233 (2001), 233–237. [7] P. Hell and X. Zhu, “Circular chromatic number of series-parallel graphs,” Journal of Graph Theory 33 (2000), no. 1, 14–24. 18 [8] A. J. W. Hilton, R. Rado and S. H. Scott, “A (< 5)-colour theorem for planar graphs,” Bulletin of the London Mathematical Society 5 (1973), 302–306. [9] K. F. Jones, “Independence in Graphs with Maximum Degree Four”, Journal of Combinatorial Theory, Series B, 37 (1984), pp. 254–269. [10] K. F. Jones, “Size and Independence in Triangle-Free Graphs with Maximum Degree Three,” Journal of Graph Theory, 14 (1990), no. 5, pp. 525–535. [11] C. Payan and M. Sakarovitch, “Ensemble cycliquement stables et graphes cubiques,” Cahiers du Centre d’Études de Recherche Opérationnelle, 17 (1975) 319–343. [12] A. Pirnazar and D. H. Ullman, “Girth and fractional chromatic number of planar graphs,” Journal of Graph Theory 39 (2002), no. 3, 201–217. [13] E. Scheinerman and D. Ullman, Fractional Graph Theory: A Rational Approach to the Theory of Graphs, Wiley, New York , 1997. xvii+211 pp. [14] W. Staton, “Some Ramsey-type numbers and the independence ratio,” Transactions of the American Mathematical Society 256 (1979), pp. 353–370. [15] R. Steinberg and C. Tovey, “Planar Ramsey Numbers,” Journal of Graph Theory, Series B, 59 (1993), pp. 288–296. [16] W. T. Tutte, A theorem on planar graphs, Transactions of the American Mathematical Society, 82 (1956), 99–116. This material is based upon work supported by the National Science Foundation under Grant No. 0200595. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. No graphs were harmed during the research of this result. This document last modified April 15, 2004. 19