10.3 Euler's Formula259a) every Halin graph is minimally 3-connected,b) every Halin graph has a Hamilton cycle.10.2.15 The medial graph of a plane graph G is the 4-regular graph M(G) withvertex set E(G) in which two vertices are joined by k edges if, in G, they arelon faces (k = 0, 1,2). (The medialadjacent edges which are incident to k ccgraph has a natural planar embedding.) Let G be a nonseparable plane graph.Showthat:a) M(G) is a 4-regular planar graph,b) M(G) = M(G*).10.3 Euler's FormulaThere is a simple formula relating the numbers of vertices, edges, and faces ina connected plane graph. It was first established for polyhedral graphs by Euler(1752), and is known as Euler's Formala.Theorem 10.19EULER'S FORMULAFor a connected plane graph G,(10.2)v(G) - e(G) + f(G) = 2Proof By induction on f(G), the ntroffacces of G. If f(G) = 1, each edge ofG is a cut edge and so G, being connected, is a tree. In this case e(G) = v(G)-1,by Theorem 4.3, and the assertion holds. Suppose that it is true for all connectedplane graphs with fewer than f faces, where f ≥ 2, and let G be a connected planegraph with f faces. Choose an edge e of G that is not a cut edge. Then G)e is aconnected plane graph with f -1 faces, because the two faces of G separated bye.coalesce to form one face of G/e.By the induction hypothesis.v(G le) -e(Gle) + f(Gle) = 2Using the relationsv(G /e) = v(G),(e(G/e)=e(G) -1, and f(G e)= f(G)-1we obtainv(G) - e(G) + f(G) = 2口The theorem follows by induction.Corollary10.20 All planarembeddings ofa connected planar graph have the samenumber of faces.10.3 Euler’s Formula 259 a) every Halin graph is minimally 3-connected, b) every Halin graph has a Hamilton cycle. 10.2.15 The medial graph of a plane graph G is the 4-regular graph M(G) with vertex set E(G) in which two vertices are joined by k edges if, in G, they are adjacent edges which are incident to k common faces (k = 0, 1, 2). (The medial graph has a natural planar embedding.) Let G be a nonseparable plane graph. Show that: a) M(G) is a 4-regular planar graph, b) M(G) ∼= M(G∗). 10.3 Euler’s Formula There is a simple formula relating the numbers of vertices, edges, and faces in a connected plane graph. It was first established for polyhedral graphs by Euler (1752), and is known as Euler’s Formula. Theorem 10.19 Euler’s Formula For a connected plane graph G, v(G) − e(G) + f(G) = 2 (10.2) Proof By induction on f(G), the number of faces of G. If f(G) = 1, each edge of G is a cut edge and so G, being connected, is a tree. In this case e(G) = v(G) − 1, by Theorem 4.3, and the assertion holds. Suppose that it is true for all connected plane graphs with fewer than f faces, where f ≥ 2, and let G be a connected plane graph with f faces. Choose an edge e of G that is not a cut edge. Then G \ e is a connected plane graph with f − 1 faces, because the two faces of G separated by e coalesce to form one face of G \ e. By the induction hypothesis, v(G \ e) − e(G \ e) + f(G \ e)=2 Using the relations v(G \ e) = v(G), e(G \ e) = e(G) − 1, and f(G \ e) = f(G) − 1 we obtain v(G) − e(G) + f(G)=2 The theorem follows by induction.
Corollary 10.20 All planar embeddings of a connected planar graph have the same number of faces