Conditions for Planarity

Conditions for Planarity

We are now going to look at some conditions to determine if a graph is planar or not.

Lemma 1: Let $G$ be a simple connected planar graph on $v$ vertices where $v \geq 3$ and $e$ edges. If the length of the shorted cycle in $G$ is $3$ (and hence the graph contains triangles), then $e \leq 3v - 6$.
  • Proof: Suppose that we have a simple connected planar graph $G$. All faces have a face degree of at least $3$, and we know that from one of the conditions in our lemma, at least one of the faces have a face degree of $3$. Hence it follows that $3f$ is the MINIMUM face degree for a graph that meets these conditions (the minimum face degree, $3$, multiplied by the number of faces, $f$). Hence it follows that:
(1)
\begin{align} 3f \leq 2e \end{align}
  • We're now going to substitute this into Euler's formula $f + v = e +2$, but we will first multiply this formula by $3$ to get $3f + 3v = 3e + 6$. Substituting the fact that $3f \leq 2e$ into this formula, we get that:
(2)
\begin{align} 2e + 3v \geq 3e + 6 $ \\ -e \geq -3v + 6 \\ e \leq 3v - 6 \quad \blacksquare \end{align}

For example, suppose that we want to show that the graph $K_5$ is not planar using Lemma 1.

We note that the length of the shorted cycle in $K_5$ is $3$:

Screen%20Shot%202014-04-08%20at%2012.46.30%20PM.png

We know that there are $5$ vertices and $10$ edges in $K_5$, hence:

(3)
\begin{align} 10 \leq 3(5) - 6 \\ 10 \leq 9 \end{align}

However this is not true. Hence $K_5$ is not planar.

Lemma 2: Let $G$ be a simple connected planar graph on $v$ vertices where $v \geq 3$ and $e$ edges. If the length of the shorted cycle in $G$ is $4$, then $e \leq 2v - 4$.
  • Proof: Suppose that we have a simple connected planar graph $G$. All faces have a face degree of at least $4$. Hence, the minimum face degree in the graph is $4$ multiplied by the number of faces in the graph. Hence it follows that:
(4)
\begin{align} 4f \leq 2e \\ 2f \leq e \end{align}
  • We will now substitute this back into Euler's formula, $f + v = e + 2$. We first multiply this formula by $2$ to get $2f + 2v = 2e + 4$, and then make the substitution in:
(5)
\begin{align} e + 2v \geq 2e + 4 \\ -e \geq -2v + 4 \\ e \leq 2v - 4 \quad \blacksquare \end{align}

We can use Lemma 2 to show that the complete bipartite graph $K_{3,3}$ is not planar. We note that the length of the shortest cycle in $K_{3,3}$ is $4$ as shown in the following diagram:

Screen%20Shot%202014-04-08%20at%201.02.20%20PM.png

There are $6$ vertices and $9$ edges in $K_{3,3}$. Applying Lemma 2 we get that:

(6)
\begin{align} 9 \leq 2(6) - 4 \\ 9 \leq 8 \end{align}

This is not true. Hence $K_{3,3}$ is not planar.

Lemma 3: Let $G$ be a simple connected planar graph on $v$ vertices where $v \geq 3$ and $e$ edges. If the length of the shorted cycle in $G$ is $g$ where $g \geq 3$, then $e \leq \frac{g(v-2)}{(g - 2)}$.
  • Proof: Suppose that we have a simple connected planar graph $G$. All faces have a face degree of at least $g$. So the sum of the face degrees is at least $gf$. Hence:
(7)
\begin{align} gf \leq 2e \end{align}
  • We are now going to substitute this into Euler's formula $f + v = e + 2$, but we first multiply this by $g$ to get $gf + gv = ge + 2g$. Then making the substitution we get:
(8)
\begin{align} 2e + gv \geq ge + 2g \\ 2e - ge \geq 2g - gv \\ (2 - g)e \geq g(2 - v) \\ -(g - 2) e \geq -g(v - 2) \\ (g - 2) e \leq g(v - 2) \\ e \leq \frac{g(v-2)}{(g - 2)} \quad \blacksquare \end{align}

Note that we can verify this general formula to be true for Lemmas 1 and 2. Suppose $g = 3$, then it follows that:

(9)
\begin{align} e \leq \frac{g(v-2)}{(g - 2)} \\ e \leq \frac{3(v - 2)}{3 - 1} \\ e \leq 3(v - 2) \\ e \leq 3v - 6 \end{align}

We can also verify this for $g = 4$:

(10)
\begin{align} e \leq \frac{g(v-2)}{(g - 2)} \\ e \leq \frac{4(v-2)}{(4 - 2)} \\ e \leq \frac{4(v-2)}{2} \\ e \leq 2(v - 2) \\ e \leq 2v - 4 \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License