Pré-visualização50 páginas

with G1 and G2.) For \u2022(G) 6 1, things become even simpler. However, the geometric operations involved require some cumbersome shifting and scaling, even if all the plane edges occurring are assumed to be straight. 4.4 Planar graphs: Kuratowski\u2019s theorem 83 The following more combinatorial route is just as easy, and may be a welcome alternative. Lemma 4.4.4. Let X be a set of 3-connected graphs. Let G be a graph [ 8.3.1 ] with \u2022(G) 6 2, and let G1; G2 be proper induced subgraphs of G such that G = G1 [G2 and jG1 \G2j = \u2022(G). If G is edge-maximal without a topological minor in X , then so are G1 and G2, and G1 \G2 = K2. Proof . Note flrst that every vertex v 2 S := V (G1 \G2) has a neigh- S bour in every component of Gi ¡ S, i = 1; 2: otherwise S r f v g would separate G, contradicting jSj = \u2022(G). By the maximality of G, every edge e added to G lies in a TX µ G + e with X 2 X . For all the X choices of e considered below, the 3-connectedness of X will imply that the branch vertices of this TX all lie in the same Gi, say in G1. (The position of e will always be symmetrical with respect to G1 and G2, so this assumption entails no loss of generality.) Then the TX meets G2 at most in a path P corresponding to an edge of X. P If S = ;, we obtain an immediate contradiction by choosing e with one end in G1 and the other in G2. If S = f v g is a singleton, let e join a neighbour v1 of v in G1 ¡ S to a neighbour v2 of v in G2 ¡ S (Fig. 4.4.3). Then P contains both v and the edge v1v2; replacing vPv1 with the edge vv1, we obtain a TX in G1 µ G, a contradiction. G1 G2 TX Pe v v1 v2 Fig. 4.4.3. If G+ e contains a TX, then so does G1 or G2 So jSj = 2, say S = fx; y g. If xy =2 G, we let e := xy, and in the x; y arising TX replace e by an x{y path through G2; this gives a TX in G, a contradiction. Hence xy 2 G, and G [S ] = K2 as claimed. It remains to show that G1 and G2 are edge-maximal without a topological minor in X . So let e0 be an additional edge for G1, say. Replacing xPy with the edge xy if necessary, we obtain a TX either in G1 + e0 (which shows the edge-maximality of G1, as desired) or in G2 (which contradicts G2 µ G). \u2044 Lemma 4.4.5. If jGj > 4 and G is edge-maximal with TK5; TK3;3 6µ G, then G is 3-connected. 84 4. Planar Graphs Proof . We apply induction on jGj. For jGj = 4, we have G = K4(4.2.9) and the assertion holds. Now let jGj > 4, and let G be edge-maximal without a TK5 or TK3;3. Suppose \u2022(G) 6 2, and choose G1 and G2 asG1; G2 in Lemma 4.4.4. For X := fK5;K3;3 g, the lemma says that G1 \G2 is a K2, with vertices x; y say. By Lemmas 4.4.4, 4.4.3 and the inductionx; y hypothesis, G1 and G2 are planar. For each i = 1; 2 separately, choose a drawing of Gi, a face fi with the edge xy on its boundary, and a vertexfi zi 6= x; y on the boundary of fi. Let K be a TK5 or TK3;3 in thezi abstract graph G+ z1z2 (Fig. 4.4.4).K G1 G2 z1 z2x y K Fig. 4.4.4. A TK5 or TK3;3 in G+ z1z2 If all the branch vertices of K lie in the same Gi, then either Gi+xzi or Gi + yzi (or Gi itself, if zi is already adjacent to x or y, respectively) contains a TK5 or TK3;3; this contradicts Corollary 4.2.9, since these graphs are planar by the choice of zi. SinceG+z1z2 does not contain four independent paths between (G1 ¡G2) and (G2 ¡G1), these subgraphs cannot both contain a branch vertex of a TK5, and cannot both contain two branch vertices of a TK3;3. Hence K is a TK3;3 with only one branch vertex v in, say, G2¡G1. But then also the graph G1 +v+f vx; vy; vz1 g, which is planar by the choice of z1, contains a TK3;3. This contradicts Corollary 4.2.9. \u2044 Theorem 4.4.6. (Kuratowski 1930; Wagner 1937) The following assertions are equivalent for graphs G: [ 4.5.1 ] [ 12.4.3 ] (i) G is planar; (ii) G contains neither K5 nor K3;3 as a minor; (iii) G contains neither K5 nor K3;3 as a topological minor. Proof . Combine Corollary 4.2.9 and Proposition 4.4.2 with Lemmas(4.2.9) 4.4.3 and 4.4.5. \u2044 Corollary 4.4.7. Every maximal planar graph with at least four ver- tices is 3-connected. Proof . Apply Lemma 4.4.5 and Theorem 4.4.6. \u2044 4.5. Algebraic planarity criteria 85 4.5 Algebraic planarity criteria In this section we show that planarity can be characterized in purely algebraic terms, by a certain abstract property of its cycle space. Theo- rems relating such seemingly distant graph properties are rare, and their signiflcance extends beyond their immediate applicability. In a sense, they indicate that both ways of viewing a graph|in our case, the topo- logical and the algebraic way|are not just formal curiosities: if both are natural enough that, quite unexpectedly, each can be expressed in terms of the other, the indications are that they have the power to reveal some genuine insights into the structure of graphs and are worth pursuing. Let G = (V;E) be a graph. We call a subset F of its edge space E(G) simple if every edge of G lies in at most two sets of F . For example, simple the cut space C\u2044(G) has a simple basis: according to Proposition 1.9.3 it is generated by the cuts E(v) formed by all the edges at a given vertex v, and an edge xy 2 G lies in E(v) only for v = x and for v = y. Theorem 4.5.1. (MacLane 1937) A graph is planar if and only if its cycle space has a simple basis. [ 4.6.3 ] Proof . The assertion being trivial for graphs of order at most 2, we (1.9.2) (1.9.6) (4.1.1) (4.2.1) (4.2.5) (4.4.6) consider a graph G of order at least 3. If \u2022(G) 6 1, then G is the union of two proper induced subgraphs G1; G2 with jG1 \G2j 6 1. Then C(G) is the direct sum of C(G1) and C(G2), and hence has a simple basis if and only if both C(G1) and C(G2) do (proof?). Moreover, G is planar if and only if both G1 and G2 are: this follows at once from Kuratowski\u2019s theorem, but also from easy geometrical considerations. The assertion for G thus follows inductively from those for G1 and G2. For the rest of the proof, we now assume that G is 2-connected. We flrst assume that G is planar and choose a drawing. By Lemma 4.2.5, the face boundaries of G are cycles, so they are elements of C(G). We shall show that the face boundaries generate all the cycles in G; then C(G) has a simple basis by Lemma 4.2.1. Let C µ G be any cycle, and let f be its inner face. By Lemma 4.2.1, every edge e with \u201de µ f lies on exactly two face boundaries G [ f 0 ] with f 0 µ f , and every edge of C lies on exactly one such face boundary. Hence the sum in C(G) of all those face boundaries is exactly C. Conversely, let fC1; : : : ; Ck g be a simple basis of C(G). Then, for every edge e 2 G, also C(G ¡ e) has a simple basis. Indeed, if e lies in just one of the sets Ci, say in C1, then fC2; : : : ; Ck g is a simple basis of C(G ¡ e); if e lies in two of the Ci, say in C1 and C2, then fC1 + C2; C3; : : : ; Ck g is such a basis. (Note that the two bases are indeed subsets of C(G¡ e) by Proposition 1.9.2.) Thus every subgraph of G has a cycle space with a simple basis. For our proof that G is planar, it thus su\u2013ces to show that the cycle spaces of K5 and K3;3 (and hence 86 4. Planar Graphs those of their subdivisions) do not have a simple basis: then G cannot contain a TK5 or TK3;3, and so is planar by Kuratowski\u2019s theorem. Let us consider K5 flrst. By Theorem 1.9.6, dim C(K5) = 6; let B = fC1; : : : ; C6 g be a simple basis, and put C0 := C1 + : : :+C6. As B is linearly independent, none of the sets C0; : : : ; C6 is empty, and so each of them contains at least three edges (cf. Proposition 1.9.2). The simplicity of B therefore implies 18 = 6 ¢ 3 6 jC1j+ : : :+ jC6j 6 2 kK5k¡ jC0j 6 2 ¢ 10¡ 3 = 17 ; a contradiction; for the middle inequality note that every edge in C0 lies in just one of the sets C1; : : : ; C6. ForK3;3, Theorem 1.9.6 gives dim C(K3;3) = 4; let B = fC1; : : : ; C4 g be a simple basis, and put C0 := C1 + : : :+C4. Since