10 Planar Graphs260Proof Let G be a planar embedding of a planar graph G. By Euler's Formula(10.2),wehavef(G) = e(G) - v(G) + 2 = e(G) - D(G) + 2Thus the number of faces of G depends only on the graph G, and not on itsembeddingCorollary 10.21Let G be asimple planar graph on at least three vertices.Thenm < 3n - 6. Furthermore, m = 3n -6 if and only if every planar embedding of Gis a triangulation.Proof It clearly suffices to prove the corollary for connected graphs. Let G be asimple connected planar graph with n ≥ 3. Consider any planar embedding G ofG. Because G is simple and connected, on at least three vertices, d(f)≥3for allf F(G).Therefore, by Theorem 10.10 and Euler's Formula (10.2)1(10.3)2m=)d(f) ≥3f(G) = 3(m-n + 2)fEF(G)or, equivalently.(10.4)m≤3n-6Equality holds in (10.4) if and only if it holds in (10.3), that is, if and only ifd(f) = 3 for each f e F(G).口Corollary 10.22 Every simple planar graph has a verter of degree at most fiveProof This is trivial for n < 3. If n ≥ 3, then by Theorem 1.1 and Corollary 10.21.8n≤d()=2m≤6n-12UEVIt follows that 8≤ 5.口We have already seen that Ks and Ks.3 are nonplanar (Theorem 10.2 andExercise 10.1.1b). Here, we derive these two basic facts from Euler's Formula (10.2)Corollary 10.23 Ks is nonplanar.Proof If Ks were planar, Corollary 10.21 would give10 =e(Ks)≤3u(Ks) -6= 9口Thus Ks must be nonplanarCorollary 10.24 K3.3 is nonplanar
260 10 Planar Graphs Proof Let G be a planar embedding of a planar graph G. By Euler’s Formula (10.2), we have f(G) = e(G) − v(G)+2= e(G) − v(G)+2 Thus the number of faces of G depends only on the graph G, and not on its embedding. Corollary 10.21 Let G be a simple planar graph on at least three vertices. Then m ≤ 3n − 6. Furthermore, m = 3n − 6 if and only if every planar embedding of G is a triangulation. Proof It clearly suffices to prove the corollary for connected graphs. Let G be a simple connected planar graph with n ≥ 3. Consider any planar embedding G of G. Because G is simple and connected, on at least three vertices, d(f) ≥ 3 for all f ∈ F(G). Therefore, by Theorem 10.10 and Euler’s Formula (10.2) 2m = f∈F (G) d(f) ≥ 3f(G) = 3(m − n + 2) (10.3) or, equivalently, m ≤ 3n − 6 (10.4) Equality holds in (10.4) if and only if it holds in (10.3), that is, if and only if d(f) = 3 for each f ∈ F(G). Corollary 10.22 Every simple planar graph has a vertex of degree at most five. Proof This is trivial for n < 3. If n ≥ 3, then by Theorem 1.1 and Corollary 10.21, δn ≤ v∈V d(v)=2m ≤ 6n − 12 It follows that δ ≤ 5. We have already seen that K5 and K3,3 are nonplanar (Theorem 10.2 and Exercise 10.1.1b). Here, we derive these two basic facts from Euler’s Formula (10.2). Corollary 10.23 K5 is nonplanar. Proof If K5 were planar, Corollary 10.21 would give 10 = e(K5) ≤ 3v(K5) − 6=9 Thus K5 must be nonplanar. Corollary 10.24 K3,3 is nonplanar.
10.3 Euler's Formula261Proof Suppose that K3.3 is planar and let G be a planar embedding of K3.3Because K3.3 has no cycle of length less than four, every face of G has degree aleast four. Therefore, by Theorem 10.10, we have4f(G) ≤d(f) = 2e(G) = 18fEFimplying that f(G)≤4. Euler's Formula (10.2) now implies that2=(G) -e(G)+ f(G)≤6- 9+4=1口which is absurd.Exercises+10.3.1 Show that the crossing number satisfies the inequality cr(G) ≥ m-3n +6,provided that n ≥ 3.10.3.2a) Let G be a connected planar graph with girth k, where h ≥ 3. Show thatm≤k(n - 2)/(k - 2).b) Deduce that the Petersen graph is nonplanar.10.3.3 Deduce Euler's Formula (10.2) from Exercise 10.2.12.10.3.4a)Showthatthecomplementofasimpleplanargraphonatleastelevenverticesb) Find a simple planar graph on eight vertices whose complement is planar.10.3.5 A plane graph is face-regular if all of its faces have the same degreea) Characterize the plane graphs which are both regular and face-regularb) Show that exactly five of these graphs are simple and 3-connected. (They arethe platonic graphs.)10.3.6 The thickness e(G) of a graph G is the minimum number of planar graphswhose union is G. (Thus e(G) = 1 if and only if G is planar.)a) Let G be a simple graph. Show that (G) ≥ [m/(3n - 6)]b)Deduce that e(K,)≥[(n +1)/61+1 and show,using Exercise 10.3.4b,thatequalityholdsforalln<8(Beineke and Harary (1965) proved that equality holds for all n + 9, 10; Battleet al. (1962) showed that 0(Ko) = 3.)
10.3 Euler’s Formula 261 Proof Suppose that K3,3 is planar and let G be a planar embedding of K3,3. Because K3,3 has no cycle of length less than four, every face of G has degree at least four. Therefore, by Theorem 10.10, we have 4f(G) ≤ f∈F d(f)=2e(G) = 18 implying that f(G) ≤ 4. Euler’s Formula (10.2) now implies that 2 = v(G) − e(G) + f(G) ≤ 6 − 9+4=1 which is absurd. Exercises 10.3.1 Show that the crossing number satisfies the inequality cr(G) ≥ m−3n+6, provided that n ≥ 3. 10.3.2 a) Let G be a connected planar graph with girth k, where k ≥ 3. Show that m ≤ k(n − 2)/(k − 2). b) Deduce that the Petersen graph is nonplanar. 10.3.3 Deduce Euler’s Formula (10.2) from Exercise 10.2.12. 10.3.4 a) Show that the complement of a simple planar graph on at least eleven vertices is nonplanar. b) Find a simple planar graph on eight vertices whose complement is planar. ————— ————— 10.3.5 A plane graph is face-regular if all of its faces have the same degree. a) Characterize the plane graphs which are both regular and face-regular. b) Show that exactly five of these graphs are simple and 3-connected. (They are the platonic graphs.) 10.3.6 The thickness θ(G) of a graph G is the minimum number of planar graphs whose union is G. (Thus θ(G) = 1 if and only if G is planar.) a) Let G be a simple graph. Show that θ(G) ≥ m/(3n − 6) . b) Deduce that θ(Kn) ≥ (n + 1)/6 + 1 and show, using Exercise 10.3.4b, that equality holds for all n ≤ 8. (Beineke and Harary (1965) proved that equality holds for all n = 9, 10; Battle et al. (1962) showed that θ(K9) = 3.)
26210 Planar Graphsc)ExpresstheTuran graph Te 13 (defined in Exercise1.1.11)as the union of twegraphs,eachisomorphictotheicosahedrond) Deduce from (b) and (c) that (K12) = 3.10.3.7a) Let G be a simple bipartite graph. Show that e(G) ≥ [m/(2n - 4)].b) Deduce that 0(Km.n) ≥[mn/(2m + 2n - 4)l.(Beineke et al. (1964) showed that equality holds if mn is even. It is conjecturedthat equality holds in all cases.)10.3.8 A plane graph is self-dual if it is isomorphic to its duala)Show thai) if G is self-dual, then e(G) = 2v(G) - 2ii) the four plane graphs shown in Figure 10.14 are self-dual.b) Find four infinite families of self-dual plane graphs of which those four graphsaremembers(Smith and Tutte (1950) proved that every self-dual plane graph belongs to oneoffour infinitefamilies.)人A区MFig. 10.14. Self-dual plane graphs10.3.9a) Let S befofrts intheplane.wheren >3 and thedistaany two points of S is at least one. Show that no more than 3n - 6 pairs ofpoints of S can be at distance exactly one(P.ERDOS)b)By considering the triangularlaice (shown in Figure 1.27) find, for eachpositive integer k, a set S of 3k? + 3k + 1 points in the plane such that thedistance between any two points of S is at least one, and such that 9k2 + 3kpairs of points of S are at distance exactly one10.3.10 THE SYLVESTER-GALLAI THEOREMa) Let C be a finite set of lines in the plane, no two of which are parallel andnotall ofwhichare concurrent.UsingEuler'sFormula(10.2),showthatsomepoint is the point of intersection of precisely two lines of C.b) Deduce from (a) the Syluester-Gallai Theorem: if S is a finite set of points inthe plane, not all of which are collinear, there is a line that contains precisely(E. MELCHIOR)two points of S
262 10 Planar Graphs c) Express the Tur´an graph T6,12 (defined in Exercise 1.1.11) as the union of two graphs, each isomorphic to the icosahedron. d) Deduce from (b) and (c) that θ(K12) = 3. 10.3.7 a) Let G be a simple bipartite graph. Show that θ(G) ≥ m/(2n − 4) . b) Deduce that θ(Km,n) ≥ mn/(2m + 2n − 4) . (Beineke et al. (1964) showed that equality holds if mn is even. It is conjectured that equality holds in all cases.) 10.3.8 A plane graph is self-dual if it is isomorphic to its dual. a) Show that: i) if G is self-dual, then e(G)=2v(G) − 2, ii) the four plane graphs shown in Figure 10.14 are self-dual. b) Find four infinite families of self-dual plane graphs of which those four graphs are members. (Smith and Tutte (1950) proved that every self-dual plane graph belongs to one of four infinite families.) Fig. 10.14. Self-dual plane graphs 10.3.9 a) Let S be a set of n points in the plane, where n ≥ 3 and the distance between any two points of S is at least one. Show that no more than 3n − 6 pairs of points of S can be at distance exactly one. (P. Erdos) ˝ b) By considering the triangular lattice (shown in Figure 1.27) find, for each positive integer k, a set S of 3k2 + 3k + 1 points in the plane such that the distance between any two points of S is at least one, and such that 9k2 + 3k pairs of points of S are at distance exactly one. 10.3.10 The Sylvester–Gallai Theorem a) Let L be a finite set of lines in the plane, no two of which are parallel and not all of which are concurrent. Using Euler’s Formula (10.2), show that some point is the point of intersection of precisely two lines of L. b) Deduce from (a) the Sylvester–Gallai Theorem: if S is a finite set of points in the plane, not all of which are collinear, there is a line that contains precisely two points of S. (E. Melchior)
10.4 Bridges26310.4 BridgesInthestudyf planargraph, certainsubgraph, calledbridges,play animportanrole. We now define these subgraphs and discuss their properties.Let H be a proper subgraph of a connected graph G. The set E(G) /E(H)may be partitioned into classes as follows.For each component F of G -V(H), there is a class consisting of the edges ofFtogether with the edges linking F to H女Each remaining edge e (that is, one which has both ends in V(H)) defines asingleton class (e].The subgraphs of G induced by these classes are the bridges of H in G. It followsmmediately from this definition that bridges of H can intersect only in verticesof H, and that any two vertices ofabridge of H are connected by a pathin thebridge that is internally disjoint from H. For a bridge B of H, the elements ofV(B) nV(H) are called its vertices of attachment to H; the remaining vertices ofB are its internal vertices. A bridge is trivial if it has no internal vertices (thatis.if it is ofthesecond type). In a connected graph, every bridge has at leastxofattachmenseparable graph, every bridge hastoreoveriat least two vertices of attachment. A bridge with k vertices of attachment iscalled a k-bridge. Two bridges with the same vertices of attachment are equivalentbridges.Figure10.15 shows a variety of bridges ofa cycle in a graph; edgesofdifferent bridges are distinguished by different kinds of lines. Bridges Bi and Bare equivalent 3-bridges; B and Bg are trivial bridges.BsBBAFig. 10.15. Bridges of a cycle
10.4 Bridges 263 10.4 Bridges In the study of planar graphs, certain subgraphs, called bridges, play an important role. We now define these subgraphs and discuss their properties. Let H be a proper subgraph of a connected graph G. The set E(G) \ E(H) may be partitioned into classes as follows. For each component F of G − V (H), there is a class consisting of the edges of F together with the edges linking F to H. Each remaining edge e (that is, one which has both ends in V (H)) defines a singleton class {e}. The subgraphs of G induced by these classes are the bridges of H in G. It follows immediately from this definition that bridges of H can intersect only in vertices of H, and that any two vertices of a bridge of H are connected by a path in the bridge that is internally disjoint from H. For a bridge B of H, the elements of V (B) ∩ V (H) are called its vertices of attachment to H; the remaining vertices of B are its internal vertices. A bridge is trivial if it has no internal vertices (that is, if it is of the second type). In a connected graph, every bridge has at least one vertex of attachment; moreover, in a nonseparable graph, every bridge has at least two vertices of attachment. A bridge with k vertices of attachment is called a k-bridge. Two bridges with the same vertices of attachment are equivalent bridges. Figure 10.15 shows a variety of bridges of a cycle in a graph; edges of different bridges are distinguished by different kinds of lines. Bridges B1 and B2 are equivalent 3-bridges; B3 and B6 are trivial bridges. B1 B2 B3 B4 B5 B6 Fig. 10.15. Bridges of a cycle
26410 Planar GraphsBRIDGES OF CYCLEWe bridges of cycles, and all bridgesbe bridges of a given cycle C. Thus, to avoid repetition, we abbreviate bridge ofC' to ‘bridge' in the coming discussionThe vertices of attachment of a k-bridge B with k ≥ 2 effect a partition ofC into k edge-disjoint paths, called the segments of B. Two bridges avoid eachotherifall thevertices of attachment of onebridge liein asinglesegment oftheother bridge:otherwise,they overlap.InFigure10.15,B2and Bavoid each otherwhereas B and B2 overlap, as do B3 and Ba. Two bridges B and B' are skew ifthere are distinct vertices of attachment u,u of B,and u.u'of B',which occur inthecyclic order u,u,,u'on C.In Figure0.15, B and B are skew, whereas andBaarenotTheorem 10.25 Overlapping bridges are either skew or else equivalent 3-bridges.Proof Suppose that bridges B and B' overlap. Clearly, each must have at leasttwo vertices of attachment. If either B or B' is a 2-bridge, it is easily verified thatthey must be skew. We may therefore assume that both B and B' have at leastthree vertices of attachmentralent bridges, then B' has a vertex u' of attachmentIf B and B' are not equiyiment u and u of B. Because B andoetweentwoconsecutiveverticesof attaB'overlap,somevertexofattachment'ofB'doesnot lieinthesegmentofBconnecting u and v. It follows that B and B' are skew.If B and B' are equivalent k-bridges, then k ≥ 3. If k ≥ 4, B and B' are skewif k =- 3, they are equivalent 3-bridges口BB:Fig. 10.16. Bridges of a cycle in a plane graphWe now consider bridges of cycles in planegraphs. Suppose that Gis aplanegraph and that C is a cycle in G. Because C is a simple closed curve in the planeeach bridge of C in G is contained in one of the two regions Int(C) or Ext(C). A
264 10 Planar Graphs Bridges of Cycles We are concerned here with bridges of cycles, and all bridges are understood to be bridges of a given cycle C. Thus, to avoid repetition, we abbreviate ‘bridge of C’ to ‘bridge’ in the coming discussion. The vertices of attachment of a k-bridge B with k ≥ 2 effect a partition of C into k edge-disjoint paths, called the segments of B. Two bridges avoid each other if all the vertices of attachment of one bridge lie in a single segment of the other bridge; otherwise, they overlap. In Figure 10.15, B2 and B3 avoid each other, whereas B1 and B2 overlap, as do B3 and B4. Two bridges B and B are skew if there are distinct vertices of attachment u,v of B, and u ,v of B , which occur in the cyclic order u,u ,v,v on C. In Figure 10.15, B3 and B4 are skew, whereas B1 and B2 are not. Theorem 10.25 Overlapping bridges are either skew or else equivalent 3-bridges. Proof Suppose that bridges B and B overlap. Clearly, each must have at least two vertices of attachment. If either B or B is a 2-bridge, it is easily verified that they must be skew. We may therefore assume that both B and B have at least three vertices of attachment. If B and B are not equivalent bridges, then B has a vertex u of attachment between two consecutive vertices of attachment u and v of B. Because B and B overlap, some vertex of attachment v of B does not lie in the segment of B connecting u and v. It follows that B and B are skew. If B and B are equivalent k-bridges, then k ≥ 3. If k ≥ 4, B and B are skew; if k = 3, they are equivalent 3-bridges. B1 B2 B3 B4 Fig. 10.16. Bridges of a cycle in a plane graph We now consider bridges of cycles in plane graphs. Suppose that G is a plane graph and that C is a cycle in G. Because C is a simple closed curve in the plane, each bridge of C in G is contained in one of the two regions Int(C) or Ext(C). A