25410 Planar Graphs(a)(6)Fig. 10.11. Isomorphic plane graphs with nonisomorphic dualsProofLetG*bethedualofG.By(i0.1)andTheorem1.1 d(f)=1口d(f*) = 2e(G*) = 2e(G) = 2mfEF(G)f*EV(G*)A simple connected plane graph in which all faces have degree three is calleda plane triangulation or, for short, a triangulation. The tetrahedron, the octahe-dron, and the icosahedron (depicted in Figure 1.14) are all triangulations. As aconsequence of (10.1) we have:Proposition 10.11 A simple connected plane graph is a triangulation if and onlyif its dual is cubicIt is easy to show that every simple plane graph on three or more vertices is aspanning subgraph of a triangulation (Exercise 10.2.5). On the other hand, as weshow in Section 10.3, no simple spanning supergraph of a triangulation is planarFor this reason, triangulaticons are also known as marimal planar graphs. Theyplay an important role in the theory of planar graphs.DELETION-CONTRACTION DUALITYLet G be a planal graph and G a planembedding of G. Foredge e of Ga plane embedding of Gle can be obtained by simply deleting the line e fromG. Thus, the deletion of an edge from a planar graph results in a planar graph.Although less obvious,the contraction of an edge ofaplanargraphalsoresults ina planar graph (Exercise 10.1.4b). Indeed, given any edge e of a planar graph Gedding G of G, the line e of G can be contracted to a single pointandaplanai(and the lines incident to its ends redrawn) so that the resulting plane graph is anar embedding of G/e.planThe following two propositions show that the operations of contracting anddeleting edges in plane graphs are related in a natural way under duality.Proposition 10.12 Let G be a connected plane graph, and let e be an edge of Gthat is not a cut edge.Then(G le)*= G* /e*254 10 Planar Graphs (a) (b) Fig. 10.11. Isomorphic plane graphs with nonisomorphic duals Proof Let G∗ be the dual of G. By (10.1) and Theorem 1.1, f∈F (G) d(f) = f ∗∈V (G∗) d(f ∗)=2e(G∗)=2e(G)=2m
A simple connected plane graph in which all faces have degree three is called a plane triangulation or, for short, a triangulation. The tetrahedron, the octahe￾dron, and the icosahedron (depicted in Figure 1.14) are all triangulations. As a consequence of (10.1) we have: Proposition 10.11 A simple connected plane graph is a triangulation if and only if its dual is cubic.
It is easy to show that every simple plane graph on three or more vertices is a spanning subgraph of a triangulation (Exercise 10.2.5). On the other hand, as we show in Section 10.3, no simple spanning supergraph of a triangulation is planar. For this reason, triangulations are also known as maximal planar graphs. They play an important role in the theory of planar graphs. Deletion–Contraction Duality Let G be a planar graph and G a plane embedding of G. For any edge e of G, a plane embedding of G \ e can be obtained by simply deleting the line e from G. Thus, the deletion of an edge from a planar graph results in a planar graph. Although less obvious, the contraction of an edge of a planar graph also results in a planar graph (Exercise 10.1.4b). Indeed, given any edge e of a planar graph G and a planar embedding G of G, the line e of G can be contracted to a single point (and the lines incident to its ends redrawn) so that the resulting plane graph is a planar embedding of G/e. The following two propositions show that the operations of contracting and deleting edges in plane graphs are related in a natural way under duality. Proposition 10.12 Let G be a connected plane graph, and let e be an edge of G that is not a cut edge. Then (G \ e) ∗ ∼= G∗ /e∗