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 graphK_5$is not planar using Lemma 1. We note that the length of the shorted cycle in$K_5$is$3$: 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. HenceK_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$4multiplied 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 graphK_{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: 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. HenceK_{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 formulaf + 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. Supposeg = 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 forg = 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}