Skip to main content

Chapter 15 Planar Graphs

A planar graph is a graph that can be drawn in the plane without crossing edges. Such a plane drawing of \(G\) has three characteristics.

  • \(v\) = number of vertices of \(G\)

  • \(e\) = number of edges of \(G\)

  • \(f\) = number of faces (regions) created by cycles in \(G\text{,}\) including the outer face.

Here is a graph with \(v=8\) and \(e=9\) and \(f=3\text{.}\) The regions are colored yellow, red and blue.

Exercises Practice Problems

1. Planar Graph Examples.

Fill in the following table for the given connected and planar graphs. Then make a conjecture!

\begin{equation*} \begin{array}{c|c|c|c|c} \mbox{Graph} & v \mbox{ (vertices)} & e \mbox{ (edges)} & f \mbox{ (faces)} & v - e + f \\ \hline C_6 &&&&\\ G &&&&\\ K_4 &&&&\\ Q &&&&\\ T &&&&\\ H &&&&\\ \end{array} \end{equation*}
2.

Let \(G\) be a connected planar graph with \(v_G\) vertices and \(e_G\) edges and \(f_G\) faces. You will use strong induction on the number of cycles \(k \geq 0\) to prove that any plane drawing of \(G\) satisfies

\begin{equation*} v_G -e_G +f_G = 2. \end{equation*}

  1. Base Case: \(k=0\). A connected graph with no cycles is a tree. We know that a tree on \(v_G\) vertices has \(v_G-1\) edges. Explain why \(v_G -e_G +f_G = 2.\)

  2. Strong Inductive Hypothesis: Assume that a plane drawing of a connected planar graph \(H\) with fewer than \(k\) cycles satisfies

    \begin{equation*} v_H - e_H + f_H = 2. \qquad \qquad {(\star)} \end{equation*}

  3. Inductive Step: Use \((\star)\) to prove that a graph \(G\) with \(k\) cycles satisfies

    \begin{equation*} v_G - e_G + f_G = 2. \end{equation*}

    Start with a plane drawing of \(G\text{.}\) Pick any edge \(e\) that is in a cycle of \(G\text{.}\) Let \(H=G-e\) be the graph you obtain by removing the edge \(e\) (but keeping the vertices).

    1. What can you say about the number of cycles in the graph \(H=G-e\text{?}\)

      We have removed an edge that was part of one or more cycles. So the number of cycles in \(H=G-e\) is strictly smaller than \(k\text{.}\)

    2. What are the following values:

      \begin{equation*} v_H = \qquad \qquad e_H = \qquad \qquad f_H = \end{equation*}

    3. Now complete the inductive step.

3. Adding the lengths of all cycles.

Let \(G\) be a planar graph whose plane drawing has regions \(A_1, A_2, \ldots, A_r\text{.}\) Let \(\mbox{len}(A_i)\) denote the number of steps you take when you walk around the boundary of region \(A_i\text{.}\) Explain why

\begin{equation*} \sum_{i=1}^f \mbox{len}(A_i) = 2 e. \end{equation*}

Start by looking at a small example planar graph to understand what this combinatorial identity is saying.

4. An upper bound on the number of faces.

Let \(G\) be a simple (no loops, no multiple edges), connected plane graph on \(v \geq 3\) vertices. Use Problem 3 to prove that

\begin{equation*} 3f \leq 2e. \end{equation*}

Hint: what is a lower bound on the number of edges in the boundary of each region?

5. An upper bound on the number of edges.

Use the fact that \(v-e+f=2\) and \(3f \leq 2e\) to prove that if \(G\) is a planar graph then

\begin{equation*} e \leq 3v -6. \end{equation*}

In other words, if \(G\) is planar it cannot have "too many" edges.

6. \(K_5\) is not planar.

In the previous problem, we showed that for any planar graph, we have \(e \leq 3v-6\text{.}\) Use this inequality to prove that \(K_5\) is not planar.

7. \(K_{3,3}\) is not planar.

The argument from Problem 5 can be generalized when we know that the planar graph \(G\) does not have any triangles (3-cycles). In this case, we must have

\begin{equation*} e \leq 2v -4. \end{equation*}

  1. Use this inequality to prove that \(K_{3,3}\) is not planar.

  2. Adapt your argument from Problem 5 to prove the following statement.

    Let \(G\) be a simple connected planar graph with \(v\) vertices, \(e\) edges and \(f\) facecs where every face is bounded by at least 4 edges. Prove that \(e \leq 2v -4\text{.}\)

8. Drawing \(K_5\) and \(K_{3,3}\) on a Torus.

If you start with a square and we glue the opposite sides to one another, we get a torus (a surface in the shape of a donut). So we can think of this square as a torus, if we identify points on opposite sides. (For example, in some classic video games, walking off the right side of the screen makes you appear at the same height on the left side of the screen.)

For example, we can draw the 4-cycle \(C_4\) using a square with opposite sides identified like so:
Using a square with opposite sides identified, show that you can draw both \(K_5\) and \(K_{3,3}\) on a torus without any crossing edges!