5.3 Planar Graphs and Euler’s Formula

1 Last edited March 21, sFormulaAmong the most ubiquitous Graphs that arise in applications are those that canbe drawn in the plane without edges crossing. For example, let s revisit theexample considered in Section of the New York City subway system. Weconsidered a graph in which vertices represent subway stops and edges representdirect train routes from one subway stop to the next. We might wonder whethersuch a graph can be drawn without any edges crossing. Why should we careabout this? Since each edge represents a subway line, the crossing of edgesrepresents two subway lines that cross paths. For that to happen, either traintracks will need to cross, an engineering feat involving careful consideration ofpotentially-conflicting schedules and the engineering of special tracks, or elsesubway lines must be built at di erent depths below ground. Both of theseoptions are costly and challenging. It turns out that the graph of the NYCsubway system cannot be drawn in such a way, and indeed many subway linesrun at di erent depths below ground in various parts of the this section we consider which Graphs can be drawn on paper withoutedges crossing and which Graphs graphGisplanarif it can be drawn in the plane in such away that no pair of edges should be paid to this definition, and in particular to the word can.

2 Whether or not a graph is Planar doesnotdepend on how it is actuallydrawn. Instead, planarity depends only on whether it can be drawn in such away. By defining this property in this more abstract way, we can ensure thatplanarity is preserved under isomorphisms. If planarity depended on how aparticular graph was drawn, then we could have two isomorphic Graphs , suchthat one is Planar and the other is not. Furthermore, Graphs that are onlydescribed abstractly through a vertex setVand an edge setE, and withoutbeing drawn, could not be described as Planar or not, since there could bemultiple ways of drawing of PlanaritySometimes it is easy to see that a particular graph is Planar , especially when itis drawn in such a way. In Examples 1, 2, and 3 of Section , we can readilysee that all Graphs are Planar , as no edges cross. However, we have noted inthe discussion of Example 6 that it is sometimes di cult to determine that aparticular graph is Planar just from looking at it.

3 For example,G1in Example 6of Section might give the mistaken impression thatK4is a non- Planar graph ,even thoughG2there makes clear that it is indeed Planar ; the two Graphs areisomorphic. These observations motivate the question of whether there exists away of looking at a graph and determining whether it is Planar or edited March 21, 2016 Euler s Formula for Planar GraphsThe most important Formula for studying Planar Graphs is undoubtedly Euler sformula, first proved by Leonhard Euler, an 18thcentury Swiss mathematician,widely considered among the greatest mathematicians that ever lived. Until nowwe have discussed vertices and edges of a graph , and the way in which thesepieces might be connected to one another. In a sense, vertices are 0-dimensionalpieces of a graph , and edges are 1-dimensional pieces. In Planar Graphs , we canalso discuss 2-dimensional pieces, which we call faces. Faces of a Planar graphare regions bounded by a set of edges and which contain no other vertex or 1 Several examples will help illustrate faces of Planar Graphs .

4 The figure belowFigure 17: A Planar graph with faces labeled using lower-case a Planar graph with several bounded regions regions are called faces, and each is bounded by a set of vertices and reasons that will become clear later, we also count the region outside ofthe graph as a face; we sometimes call this the outside discovered a beautiful result about Planar Graphs that relates the num-ber of vertices, edges, and faces. In what follows, we usev=|V|to denote thenumber of vertices in a graph ,e=|E|to denote the number of edges in a graph ,andfto denote its number of faces. Using these symbols, Euler s showed thatfor any connected Planar graph , the following relationship holds:v e+f=2.(47)In the graph above in Figure 17,v= 23,e= 30, andf= 9, if we rememberto count the outside face. Indeed, we have 23 30 + 9 = 2. This relationshipholds for all connected Planar edited March 21, 2016 Example 2An infinite set of Planar Graphs are those associated with polygons.

5 The figurebelow illustrates several Graphs associated with regular polyhedra. Of course,Figure 18: Regular polygonal Graphs with 3, 4, 5, and 6 graph contains the same number of edges as vertices, sov e+f=2becomes merelyf= 2, which is indeed the case. One face is inside thepolygon, and the other is 3A special type of graph that satisfies Euler s Formula is a tree. A tree is a graphsuch that there is exactly one way to travel between any vertex to any othervertex. These Graphs have no circular loops, and hence do not bound any there is only the one outside face in this graph , Euler s Formula gives usFigure 19: A tree graph there are no faces except for the outside e+ 1 = 2, which simplifies tov e= 1 ore=v 1. Every tree satisfiesthis relationship and so always has one fewer edges than it has of a FaceIn the same way that we were able to characterize a vertex by counting thenumber of edges adjacent to it, we can also characterize a face by its number ofedges (or equivalently vertices) on its boundary.

6 For example, consider Figure20, which shows a graph we considered earlier. Here each face is labeled by its52last edited March 21, 2016 Figure 20: A Planar graph with each face labeled by its of edges. We use the worddegreeto refer to the number of edges of a facefis the number of edges along its bound-ary. Alternatively, it is the number of vertices along its boundary. Alternatively,it is the number of other faces with which it shares an edge. The degree of avertexfis oftentimes writtendeg(f).Every edge in a Planar graph is shared by exactly two faces. This observationleads to the following all Planar Graphs , the sum of degrees over all faces is equalto twice the number of edges. In symbols,Pideg(fi)=2|E|, wherefiare thefaces of the result might be seen as an analogue of a result we saw earlier involvingthe sum of degrees of all vertices (Theorem 7). These theorems help us under-stand the relationship between the number of edges in a graph and the verticesand faces of a ( Planar ) definition of a graph (as a setVand a setEconsisting of two-elementsubsets ofV) requires that there be at most one edge connecting any two ver-tices.

7 To understand this, consider two verticesaandb. We have learned before(in Section 2) that sets do not have duplicate elements. Therefore, the set ofedgesEcan only contain the element{a,b}one time. Such Graphs are calledsimpleand they have been the exclusive focus of our consideration in this sec-tion. Because our Graphs are all simple, the smallest possible degree of a face is3, since a face with degree two would require that two edges connect a pair can use this result, along with Theorem 9, to obtain an important resultabout Planar Graphs . In particular, notice that since the degree of every facemust be at least 3, we havePi3 Pideg(fi). The left-hand side, however,evaluates to 3|F|,where|F|is the number of faces in the Planar graph , becausewe are adding 3 for every face. Theorem 9 tells us that the right-hand side is53last edited March 21, 2016equal to 2|E|,where|E|is the number of edges in the graph . Therefore, we canconclude:Theorem all Planar Graphs ,3|F| 2|E|, where|F|is the number offaces and|E|is the number of , of course, is equivalent to stating that|E| 32|F|; the number of facesof a Planar graph ensures that we have at least a certain number of ofK5We can use Euler s Formula to prove that non-planarity of the complete graph (or clique) on 5 vertices,K5, illustrated below.

8 This graph hasv=5verticesFigure 21: The complete graph on five vertices, 10 edges, so Euler s Formula would indicate that it should havef=7faces. We have just seen that for any Planar graph we havee 32f, and so inthis particular case we must have at least327 = edges. However,K5onlyhas 10 edges, which is of course less than , showing thatK5cannot be aplanar in Non- Planar GraphsNon- Planar Graphs do not technically have faces there does not seem to beany good way to discuss faces in cases when edges cross one