Graph Theory Il Finally, as we'll see shortly, planar graphs reveal a fundamental truth about the structure of our three-dimensional world 3.1 Euler's Formula A drawing of a planar graph divides the plane into faces, regions bounded by edges of the graph. For example, the drawing below has four faces Face 1, which extends off to infinity in all directions, is called the outside face. It turns out that the number of vertices and edges in a connected planar graph determine the number of faces in every drawing Theorem 4(Euler's Formula). For every drawing of a connected planar graph e+f=2 where v is the number of vertices, e is the number of edges, and fis the number of faces For example, in the drawing above, V=4, E=6, and f= 4. Sure enough, 4-6+4 2, as Euler's Formula claims Proof. We use induction on the number of edges in the graph. Let P(e) be the proposition that v-e+f= 2 for every drawing of a graph G with e edges Base case: A connected graph with e =0 edges has u=1 vertices, and every drawing of the graph has f =l faces(the outside face). Thus, v-e+f=1-0+1=2, and so P(O) Inductive step: Now we assume that P(e) is true in order to prove P(e+1)wheree 20 Consider a connected graph G with e +1 edges. There are two cases 1. IfG is acylic, then the graph is a tree. Thus, there are e+2 vertices and every drawing has only the outside face. Since(e+2)-(e+1)+1=2-1+1=2, P(n+1)is true 2. Otherwise, G has at least one cycle. Select a spanning tree and an edge(u, a )in the cycle, but not in the tree. (The spanning tree can not contain all edges in the cle, since trees are acyclic. Removing(u, u)merges the two faces on either side of the edge and leaves a graphG with only e edges and some number of vertices v and faces f. Graph G is connected, because there is a path between every pair of vertices within the spanning tree. So u-e+ f =2 by the induction assumption P(e). Thus, the original graph G had v vertices, e+ 1 edges, and f+1 faces. Since v(e+1)+(+1)=v-e+f=2, P(n+ 1)is again trueGraph Theory II 7 Finally, as we’ll see shortly, planar graphs reveal a fundamental truth about the structure of our three­dimensional world. 3.1 Euler’s Formula A drawing of a planar graph divides the plane into faces, regions bounded by edges of the graph. For example, the drawing below has four faces: 1 2 3 4 Face 1, which extends off to infinity in all directions, is called the outside face. It turns out that the number of vertices and edges in a connected planar graph determine the number of faces in every drawing: Theorem 4 (Euler’s Formula). For every drawing of a connected planar graph v − e + f = 2 where v is the number of vertices, e is the number of edges, and fis the number of faces. For example, in the drawing above, |V | = 4, | | E = 6, and f = 4. Sure enough, 4−6+4 = 2, as Euler’s Formula claims. Proof. We use induction on the number of edges in the graph. Let P(e) be the proposition that v − e + f = 2 for every drawing of a graph G with e edges. Base case: A connected graph with e = 0 edges has v = 1 vertices, and every drawing of the graph has f = 1 faces (the outside face). Thus, v − e + f = 1 − 0 + 1 = 2, and so P(0) is true. Inductive step: Now we assume that P(e) is true in order to prove P(e + 1) where e ≥ 0. Consider a connected graph G with e + 1 edges. There are two cases: 1. If G is acylic, then the graph is a tree. Thus, there are e+2 vertices and every drawing has only the outside face. Since (e + 2) − (e + 1) + 1 = 2 − 1 + 1 = 2, P(n + 1) is true. 2. Otherwise, G has at least one cycle. Select a spanning tree and an edge (u, v) in the cycle, but not in the tree. (The spanning tree can not contain all edges in the cycle, since trees are acyclic.) Removing (u, v) merges the two faces on either side of the edge and leaves a graph G� with only e edges and some number of vertices v and faces f. Graph G� is connected, because there is a path between every pair of vertices within the spanning tree. So v − e + f = 2 by the induction assumption P(e). Thus, the original graph G had v vertices, e + 1 edges, and f + 1 faces. Since v − (e + 1) + (f + 1) = v − e + f = 2, P(n + 1) is again true