# Planar Graphs & Euler’s Theorem

A **planar graph** is a graph which can be drawn in the plane without any edges crossing. Some pictures of a planar graph might have crossing edges, but it’s possible to redraw the picture to eliminate the crossings.

There are also many practical applications with a graph structure in which crossing edges are a nuisance, including design problems for circuits, subways, utility lines. Two crossing connections normally means that the edges must be run at different heights.

When a planar graph is drawn with no crossing edges, it divides the plane into a set of regions, called *faces*. By convention, we also count the unbounded area outside the whole graph as one face.

Suppose that we have a graph with e edges, v nodes, and f faces. We know that the Handshaking theorem holds, i.e. the sum of the degrees of the vertices is 2e. For planar graphs, we also have a Handshaking theorem for faces: the sum of the face degrees is 2e.

For connected planar graphs, we have Euler’s formula: v − e + f = 2. We’ll prove that this formula works.

Before we try to prove Euler’s formula, let’s look at one special type of planar graph: **trees**.

A tree doesn’t divide the plane into multiple regions, because it doesn’t contain any cycles. In graph theory, *a tree has only one face*: the entire plane surrounding it. So Euler’s theorem reduces to v − e = 1,

i.e. e = v − 1. Let’s prove that this is true, by induction.

*Proof by induction on the number of edges in the graph*.

Base Case: If the graph contains no edges and only a single vertex, the formula is clearly true.

IHOP: Suppose the formula works for all trees with up to k vertices. Let T be a tree with k + 1 vertices.

We need to show that T has k edges.

Now, we ﬁnd a vertex with degree 1 (only one edge going into it). To do this start at any vertex r and follow a path in any direction, without repeating edges. Because T has no cycles, this path can’t return to any vertex it has already visited. So it must eventually hit a dead end: the vertex at the end must have degree 1. Call it p.

Remove p and the edge coming into it, making a new tree T′ with k vertices. By the IHOP, T′ has k − 1 edges. So T has k edges. Therefore the formula holds for T.

We can now prove **Euler’s Formula** (*v − e + f = *2) works in general, for any connected planar graph.

*Proof by induction on the number of edges in the graph.*

Base Case: If e = 0, the graph consists of a single node with a single face surrounding it. So we have 1 − 0 + 1 = 2 which is clearly right.

IHOP: Suppose the formula works for all graphs with no more than n edges. Let G be a graph with n + 1 edges.

Case 1: G doesn’t contain a cycle. So G is a tree and we already know the formula works for trees since we proved it! Check!

Case 2: G contains at least one cycle. Pick an edge p that’s on a cycle. Remove p to create a new graph G′.

Since the cycle separates the plane into two faces, the faces to either side of p must be distinct. When we remove the edge p, we merge these two faces. So G′ has one fewer faces than G.

Since G′ has n edges, the formula works for G′ by the IHOP.

That is, v′ − e′ + f′ = 2.

But v′ = v, e′ = e − 1, and f′ = f − 1.

Substituting, we ﬁnd that

v − (e − 1) + (f − 1) = 2

So, v − e + f = 2 as desired.

## Exam Time!

Use Euler’s Planar Graph Theorem to prove whether the graph is planar or nonplanar.

http://www.science4all.org/le-nguyen-hoang/eulers-formula-and-the-utilities-problem/

## Leave a Reply