Pré-visualização50 páginas

K3;3 has girth 4, each Ci contains at least four edges, so 16 = 4 ¢ 4 6 jC1j+ : : :+ jC4j 6 2 kK3;3k¡ jC0j 6 2 ¢ 9¡ 4 = 14 ; a contradiction. \u2044 It is one of the hidden beauties of planarity theory that two such abstract and seemingly unintuitive results about generating sets in cy- cle spaces as MacLane\u2019s theorem and Tutte\u2019s theorem 3.2.3 conspire to produce a very tangible planarity criterion for 3-connected graphs: Theorem 4.5.2. (Tutte 1963) A 3-connected graph is planar if and only if every edge lies on at most (equivalently: exactly) two non-separating induced cycles. Proof . The forward implication follows from Propositions 4.2.10 and (3.2.3) (4.2.1) (4.2.5) (4.2.10) 4.2.1 (and Proposition 4.2.5 for the \u2018exactly two\u2019 version); the backward implication follows from Theorems 3.2.3 and 4.5.1. \u2044 4.6 Plane duality 87 4.6 Plane duality In this section we shall use MacLane\u2019s theorem to uncover another con- nection between planarity and algebraic structure: a connection between the duality of plane graphs, deflned below, and the duality of the cycle and cut space hinted at in Chapters 1.9 and 3.5. A plane multigraph is a pair G = (V;E) of flnite sets (of vertices planemultigraph and edges, respectively) satisfying the following conditions: (i) V µ R2; (ii) every edge is either an arc between two vertices or a polygon containing exactly one vertex (its endpoint); (iii) apart from its own endpoint(s), an edge contains no vertex and no point of any other edge. We shall use terms deflned for plane graphs freely for plane multigraphs. Note that, as in abstract multigraphs, both loops and double edges count as cycles. Let us consider the plane multigraph G shown in Figure 4.6.1. Let us place a new vertex inside each face of G and link these new vertices up to form another plane multigraph G\u2044, as follows: for every edge e of G we link the two new vertices in the faces incident with e by an edge e\u2044 crossing e; if e is incident with only one face, we attach a loop e\u2044 to the new vertex in that face, again crossing the edge e. The plane multigraph G\u2044 formed in this way is then dual to G in the following sense: if we apply the same procedure as above to G\u2044, we obtain a plane multigraph very similar to G; in fact, G itself may be reobtained from G\u2044 in this way. G\u2044 e\u2044e G Fig. 4.6.1. A plane graph and its dual To make this idea more precise, let G = (V;E) and (V \u2044; E\u2044) be any two plane multigraphs, and put F (G) =: F and F ((V \u2044; E\u2044)) =: F \u2044. We call (V \u2044; E\u2044) a plane dual of G, and write (V \u2044; E\u2044) =: G\u2044, if there are planedual G\u2044 bijections F !V \u2044 f 7! v\u2044(f) E!E\u2044 e 7! e\u2044 V !F \u2044 v 7! f\u2044(v) satisfying the following conditions: (i) v\u2044(f) 2 f for all f 2 F ; 88 4. Planar Graphs (ii) je\u2044 \Gj = j\u201de\u2044 \\u201dej = je\G\u2044j = 1 for all e 2 E; (iii) v 2 f\u2044(v) for all v 2 V . The existence of such bijections implies that both G and G\u2044 are con- nected (exercise). Conversely, every connected plane multigraph G has a plane dual G\u2044: if we pick from each face f of G a point v\u2044(f) as a vertex for G\u2044, we can always link these vertices up by independent arcs as required by condition (ii), and there is always a bijection V ! F \u2044 satisfying (iii) (exercise). If G\u20441 and G \u2044 2 are two plane duals of G, then clearly G \u2044 1 \u2019 G\u20442; in fact, one can show that the natural bijection v\u20441(f) 7! v\u20442(f) is a topological isomorphism between G\u20441 and G \u2044 2. In this sense, we may speak of the plane dual G\u2044 of G. Finally, G is in turn a plane dual of G\u2044. Indeed, this is witnessed by the inverse maps of the bijections from the deflnition of G\u2044: setting v\u2044(f\u2044(v)) := v and f\u2044(v\u2044(f)) := f for f\u2044(v) 2 F \u2044 and v\u2044(f) 2 V \u2044, we see that conditions (i) and (iii) for G\u2044 transform into (iii) and (i) for G, while condition (ii) is symmetrical in G and G\u2044. Thus, the term \u2018dual\u2019 is also formally justifled. Plane duality is fascinating not least because it establishes a con- nection between two natural but very difierent kinds of edge sets in a multigraph, between cycles and cuts: Proposition 4.6.1. For any connected plane multigraph G, an edge set[ 6.5.2 ] E µ E(G) is the edge set of a cycle in G if and only if E\u2044 := f e\u2044 j e 2 E g is a minimal cut in G\u2044. Proof . By conditions (i) and (ii) in the deflnition of G\u2044, two vertices(4.1.1)(4.2.3) v\u2044(f1) and v\u2044(f2) of G\u2044 lie in the same component of G\u2044¡ E\u2044 if and only if f1 and f2 lie in the same region of R2r S E: every v\u2044(f1){v\u2044(f2) path in G\u2044¡E\u2044 is an arc between f1 and f2 in R2r S E, and conversely every such arc P (with P \V (G) = ;) deflnes a walk in G\u2044¡E\u2044 between v\u2044(f1) and v\u2044(f2). Now if C µ G is a cycle and E = E(C) then, by the Jordan curve theorem and the above correspondence, G\u2044¡E\u2044 has exactly two com- ponents, so E\u2044 is a minimal cut in G\u2044. Conversely, if E µ E(G) is such that E\u2044 is a cut in G\u2044, then, by Proposition 4.2.3 and the above correspondence, E contains the edges of a cycle C µ G. If E\u2044 is minimal as a cut, then E cannot contain any further edges (by the implication shown before), so E = E(C). \u2044 Proposition 4.6.1 suggests the following generalization of plane du- ality to a notion of duality for abstract multigraphs. Let us call a multi- graph G\u2044 an abstract dual of a multigraph G if E(G\u2044) = E(G) and theabstractdual minimal cuts in G\u2044 are precisely the edge sets of cycles in G. Note that any abstract dual of a multigraph is connected. 4.6 Plane duality 89 Proposition 4.6.2. If G\u2044 is an abstract dual of G, then the cut space of G\u2044 is the cycle space of G, i.e. C\u2044(G\u2044) = C(G) : Proof . By Lemma 1.9.4,5 C\u2044(G\u2044) is the subspace of E(G\u2044) = E(G) (1.9.4) generated by the minimal cuts in G\u2044. By assumption, these are precisely the edge sets of the cycles in G, and these generate C(G) in E(G). \u2044 We flnally come to one of the highlights of classical planarity the- ory: the planar graphs are characterized by the fact that they have an abstract dual. Although less obviously intuitive, this duality is just as fundamental a property as planarity itself; indeed the following theorem may well be seen as a topological characterization of the graphs that have a dual: Theorem 4.6.3. (Whitney 1933) A graph is planar if and only if it has an abstract dual. Proof . Let G be a graph. If G is plane, then every component C of G has (1.9.3)(4.5.1) a plane dual C\u2044. Let us consider these C\u2044 as abstract multigraphs, pick a vertex in each of them, and identify these vertices. In the connected multigraph G\u2044 obtained, the set of minimal cuts is the union of the sets of minimal cuts in the multigraphs C\u2044. By Proposition 4.6.1, these cuts are precisely the edge sets of the cycles in G, so G\u2044 is an abstract dual of G. Conversely, suppose that G has an abstract dual G\u2044. By Theorem 4.5.1 and Proposition 4.6.2 it su\u2013ces to show that C\u2044(G\u2044) has a simple basis, which it has by Proposition 1.9.3. \u2044 Exercises 1. Show that every graph can be embedded in R3 with all edges straight. 2.¡ Show directly by Lemma 4.1.2 that K3;3 is not planar. 3.¡ Find an Euler formula for disconnected graphs. 4. Show that every connected planar graph with n vertices, m edges and flnite girth g satisfles m 6 g g¡2 (n¡ 2). 5. Show that every planar graph is a union of three forests. 5 Although the lemma was stated for graphs only, its proof remains the same for multigraphs. 90 4. Planar Graphs 6. Let G1; G2; : : : be an inflnite sequence of pairwise non-isomorphic graphs. Show that if lim sup "(Gi) > 3 then the graphs Gi have un- bounded genus|that is to say, there is no (closed) surface S in which all the Gi can be embedded. (Hint. You may use the fact that for every surface S there is a constant ´(S) 6 2 such that every graph embedded in S satisfles the generalized Euler formula of n¡m+ \u2018 > ´(S).) 7. Find a direct proof for planar graphs of Tutte\u2019s theorem on the cycle space of 3-connected