Graph Theory: Euler’s Formula for Planar Graphs
Planar graphs are a special type of graph that have many applications and arise often in the study of graph theory.
This posts introduces planar graphs, where they arise and their applications, and Euler’s formula, a fundamental idea for studying these graphs. If you are new to graph theory, fell free to check out this article, but I’ll explain all needed background in this post.
Graphs 101
This section gives a short introduction to graph theory, but feel free to skip below if you have basic familiarity with the topic.
Graph theory is the study of pairwise relationships, which mathematicians choose to represent as graphs. A graph is a structure of vertices or nodes connected by edges or lines. Graphs are exciting to work with, and they are great models for things we use every day, like a map of a town or how you surf the internet.
In the figure above, the vertices represent websites, and the links represent which websites have links to other websites. Notice how Google is a major search engine that sends users all over the internet. In this graph, Google has 8 edges attached to it. YouTube, which is a large but smaller than Google, only has 6 edges attached to it.
Formally, a graph has the following mathematical definition.
Definition: A graph G=(V, E) is a set of vertices V and edges E that are made up of pairs of vertices.
This is the barebones introduction to graphs and graph theory, but there is much more to the subject. See this article for a more in depth introductory discussion of the subject and its applications, or continue to learn about planar graphs.
Planar Graphs
A planar graph is one special type of graph, which is defined as any graph that can be drawn on a flat piece of paper without crossing 2 edges. These graphs are interesting because often graphs that don’t appear planar can be redrawn without edges crossing.
This type of structure arises in many different cases including mapping out a set of streets in a town or designing a network to model movement through a mesh grid. In the figure below, a road map seen on the left is converted into a planar graph on the right, by placing vertices at intersections and edges along roads connecting intersections.
As long as no 2 roads (edges) cross over one another, the graph is planar. Since the roads only meet at intersections in this case (and any case where there are no over or underpasses), it is a planar graph.
When the graph covers the town, intersections and roads can be clearly identified. Another key feature of the town is a block or a region that you can walk around without crossing any streets. This notion of a block has an analogue in planar graphs.
Definition: Faces of a planar graph are regions of the plane that are bounded by sets of edges from the graph and contain no additional edges or vertices.
The analogue of a block in the town is a face of the planar graph. The figure below, the faces are clearly labeled a-i. The faces a-h are interior faces of the graph, regions that are strictly inside. Face i is the exterior face of the graph, that contains the rest of the plane outside of the graph.
The set of faces for a graph G is denoted as F, similar to the vertices V or edges E. Faces are a critical idea in planar graphs and will be used in Euler’s Theorem.
Euler’s Theorem
Euler’s Formula: Given a planar graph G=(V,E) and faces F,|V|-|E|+|F|=2.
In the above theorem or formula, |V|, |E|, and |F| denote the number of vertices, edges, and faces of the graph G respectively. No matter how a planar graph is drawn, any edge or vertices can be moved as long as no 2 edges cross, the relationship |V|- |E| + |F| = 2 will always be true.
Proof
The below is a sketch for how to prove Euler’s formula. Typically, this proof involves induction on the number of edges or vertices. The below proof isn’t the most rigorous, but it should provide an outline and you can fill in some of the holes as needed.
Proof: Let G=(V,E) be a graph. To use induction on the number of edges |E|, consider a graph with only 1 vertex and 0 edges. This graph has 1 face, the exterior face, so 1– 0+ 1 = 2 shows that Euler’s Theorem holds for the base case. For the inductive step, assume Euler’s Theorem holds for all graphs with |E|=n. Consider a planar graph graph G=(V, E), with faces F, such that |E|=n+1. There are 2 cases:
Case 1: G=(V, E) is a tree. All trees have |V| = |E| + 1 (this fact and the proof of this could be expanded on if you haven’t worked with trees before). Additionally, since trees have no cycles, by definition, a tree has no interior faces, and there only exist an exterior face. This gives |F| = 1. Plugging in these values into the equation, we have |V|- |E| + |F| = |E| + 1-|E| + 1 = 2, so Euler’s Theorem holds when G is a tree.
Case 2: G(V, E) contains cycles. In this case, let p be an edge in a cycle in G. Let G’ be the graph of G with edge P removed, i.e. G’=(V,E\{p}). This gives the relationship |E’| = |E|-1. Since p was an edge in a cycle, it separated 2 distinct faces, so removing it reduces the number of faces for G’. Namely |F’| = |F|-1. Since G has n+1 edges, it follows that G’ has n edges, and by the inductive hypothesis |V’|-|E’|+|F’| = 2. Based on how G’ was constructed, we have the relationships that |V’|=|V|, |E’|=|E|-1, and |F’|=|F|-1. Substituting these values into the equation, |V|-(|E|-1)+|F|-1 = |V|-|E|+|F|=2.
Since Euler’s Theorem is true for the base case and the inductive cases, we conclude Euler’s Theorem must be true.
The above is one route to prove Euler’s formula, but there are many others.
Planar graphs, the relationships between vertices, faces, and edges, graph embeddings in other shapes are very interesting to study and a field with many questions. I hope to write more about these soon.
If you made it this far, hit the clap button. I’m new to Medium, and trying to crank out some content about how I think about math, data science, and computers. Follow me that’s if your sort of thing. Twitter: @JoshuaPickard_
