Planar Graphs

When is it possible to draw a graph so that none of the edges cross? If this is possible, we say the graph is planar (since you can draw it on the plane).

Notice that the definition of planar includes the phrase “it is possible to.” This means that even if a graph does not look like it is planar, it still might be. Perhaps you can redraw it in a way in which no edges cross. For example, this is a planar graph:

The graphs are the same, so if one is planar, the other must be too. However, the original drawing of the graph was not a planar representation of the graph.

When a planar graph is drawn without edges crossing, the edges and vertices of the graph divide the plane into regions. We will call each region a face. The graph above has 3 faces (yes, we do include the “outside” region as a face). The number of faces does not change no matter how you draw the graph (as long as you do so without the edges crossing), so it makes sense to ascribe the number of faces as a property of the planar graph.

WARNING: you can only count faces when the graph is drawn in a planar way. For example, consider these two representations of the same graph:

If you try to count faces using the graph on the left, you might say there are 5 faces (including the outside). But drawing the graph with a planar representation shows that in fact there are only 4 faces.

There is a connection between the number of vertices (\(v\)), the number of edges (\(e\)) and the number of faces (\(f\)) in any connected planar graph. This relationship is called Euler's formula.

Euler's Formula for Planar Graphs.

For any (connected) planar graph with \(v\) vertices, \(e\) edges and \(f\) faces, we have

\begin{equation*} v-e + f = 2\text{.} \end{equation*}

Why is Euler's formula true? One way to convince yourself of its validity is to draw a planar graph step by step. Start with the graph \(P_2\text{:}\)

Any connected graph (besides just a single isolated vertex) must contain this subgraph. Now build up to your graph by adding edges and vertices. Each step will consist of either adding a new vertex connected by a new edge to part of your graph (so creating a new “spike”) or by connecting two vertices already in the graph with a new edge (completing a circuit).

What do these “moves” do? When adding the spike, the number of edges increases by 1, the number of vertices increases by one, and the number of faces remains the same. But this means that \(v - e + f\) does not change. Completing a circuit adds one edge, adds one face, and keeps the number of vertices the same. So again, \(v - e + f\) does not change.

Since we can build any graph using a combination of these two moves, and doing so never changes the quantity \(v - e + f\text{,}\) that quantity will be the same for all graphs. But notice that our starting graph \(P_2\) has \(v = 2\text{,}\) \(e = 1\) and \(f = 1\text{,}\) so \(v - e + f = 2\text{.}\) This argument is essentially a proof by induction. A good exercise would be to rewrite it as a formal induction proof.