Skip to main content

Section 5.1 Euler's formula

Easily the most influential and widely studied result in graph theory is the Four Color Theorem. We have already studied the chromatic number of a graph in general; the Four Color Theorem deals with the chromatic number of graphs that can be drawn in the plane without any edges crossing (since it is these graphs that model coloring the regions in a map of a country, for example). We call such graphs planar.

Given the proofs we have seen of Theorem 4.1.4 and Theorem 4.2.4 , we might hope that there would be some helpful property that all planar graphs had that would allow us to make a similar sort of inductive coloring argument. For example, if we knew that every planar graph had minimal degree no more than 3, the proof would be easy: let \(v\) be a vertex of degree 3, inductively color \(G-v\) with four color, and color \(v\) with the color not present in any of its three neighbors.

Obviously this cannot be the case; there is a planar graph in which every vertex has degree 4 or more [ex?]. But perhaps there is something we can say about the minimal degree or maximal degree of planar graphs. Or at very least, about the relationship between the numbers of vertices and edges.

First let's consider graphs that are maximal planar. That is, graphs that are planar but for which any added edge to the graph would make the graph non-planar.

Activity 17.

Find some examples of graphs that are not maximal planar and some that are. What must be true of all the faces (regions) in a maximal planar graph?

Note that if a face of a planar graph is bounded by a cycle of length 4 or more, then we can add an edge between non-adjacent vertices in that cycle and still have a planar graph.

Suppose that \(G\) is maximal planar. First notice that a graph cannot contain a region bounded by a triangle if it has fewer than 3 vertices. Hence the number of vertices in \(G\) is \(\ge 3\text{.}\) By means of contradiction assume that our maximal planar graph \(G\) has a region that is not a triangle. \(G\) is connected. If not, then we could add an edge between the outer boundary of any two components. Furthermore, the boundary of an edge is a cycle. If this was not the case, if the boundary of an edge was acyclic, then we would have a tree with at least three vertices. Adding any edge to a tree on three or more vertices results in a planar graph, so the original tree was not maximal planar. Now suppose that \(G\) is a cycle with trees branching off the cycle. Since a tree has at least 2 vertices of degree 1 or leaves, there must be one leaf that is not in a cycle. So, we can add an edge from this leaf to any vertex in the cycle that is not also in that leaf’s tree. Again, this contradicts \(G\) being maximally planar. Therefore, the boundary of each region in \(G\) is simply a cycle.

Now, the region that is not a triangle must have 3 consecutive vertices on its boundary, call them \(v_1, v_2,\) and \(v_3\text{,}\) where edges \(v_1v_2\) and \(v_2v_3\) are edges of \(G\) but \(v_1v_3\) is not. This means we can add in the edge \(v_1v_3\) to \(G\text{,}\) contradicting \(G\) being maximally planar. Therefore, every region of a maximal planar graph on 3 or more vertices is a triangle.

Now, suppose that every face in planar drawing of a graph \(G\) is a triangle. \(G\) is a planar graph meaning that it can be drawn in the plane without any edges crossing. Choose any vertex \(v_1\) and vertex \(v_2\) such that the \(v_1\) and \(v_2\) are not adjacent. Starting at vertex \(v_1\) if we attempt to add in the edge connecting \(v_1\) and \(v_2\) we have to enter and exit at least one triangular region that \(v_2\) is not a part of. Therefore, adding one more edge would make \(G\) no longer planar, hence \(G\) is maximal planar.

In drawing a bunch of maximal planar graphs, we notice that there appears to be a strict relationship between the number of vertices and number of edges any such graph. For three vertices, maximal planar graphs have three edges. With four vertices, six edges. With five vertices, nine edges. We therefore consider the following conjecture.

[Is there a direct proof of this conjecture that doesn't first prove Euler's formula?]

We will prove this conjecture by first proving a more general relationship between the number of vertices, edges, and faces in any planar graph.

The following is an intuitive argument for Euler's Formula. Let \(G\) be a planar graph. By Proposition 2.0.4, we know that every graph contains a spanning tree, so prune \(G\) down to its spanning tree. By Theorem 2.0.5 we know that the pruned \(G\) has \(v\) vertices and \(v-1\text{,}\) or \(e=v-1\text{.}\) Since the pruned \(G\) is a spanning tree, we know it only has one face, satisfying Euler's Formula (\(v-(v-1)+1=2\)).

From topology, we then know that whenever a cycle is formed, a face is added. So when we put the original edges of \(G\) back in, we create \(k\) cycles, one for each of the \(k\)edges we added back in, and therefore create \(k\) faces. Therefore the number of edges and faces added to the graph offset and Euler's Formula is still satisfied for our original \(G\) (\(v-(v-1+k)+(1+k)=2\)).

We can now prove Conjecture 5.1.2 and a simple strengthening of it to all planar graphs.

We can use Euler's formula to easily prove that certain graphs are not planar.

Example 5.1.5.

Prove the \(K_5\) is not planar, using Theorem 5.1.3 or Corollary 5.1.4.

Solution

Note that \(K_5\) has 5 vertices and 10 edges. Suppose that \(K_5\) was planar. Then Corollary 5.1.4 says that \(10 \le 3 \cdot 5 -6\) which implies that \(10 \le 9\text{.}\) Clearly this is a contradiction so \(K_5\) is not planar.

As one final application of Euler's formula, we will prove a useful fact about the minimum degree of any planar graph.

Let \(G\) be a planer graph with \(|V|=p\) vertices and \(|E|=q\) edges. To prove this Corollary, we use the contrapositive, if every vertex in graph \(G\) has degree of at least 6 or \(\delta(G) \ge 6\text{,}\) then the graph \(G\) is not planer. We will use Corollary 5.1.4 which states that any planar graph with p vertices has \(q \le 3p-6\) edges to reach the contradiction. Notice that in our graph \(G\text{,}\) we have at least 7 vertices because in order for the minimum degree of \(G\) to be 6, \(G\) needs to have at least one vertex that is adjacent to 6 other vertices (1+6=7 vertices). So, \(p \ge 7\text{.}\) We know that in general \(2q = \sum deg(v)\) and in this particular graph \(G\text{,}\) every vertex has degree of at least 6. Hence, \(\sum deg(v) \ge 6p\) which means that \(2q \ge 6p\) or \(q \ge 3p\text{.}\) However, notice that we also have that \(q \ge 3p \gt 3p-6\text{.}\) This is a contradiction of Corollary 5.1.4. Therefore, we can conclude that in every graph that does not have a vertex of degree five or less must be non-planer because if a graph is planer then this statement holds.