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:
- 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:
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$:

We know that there are $5$ vertices and $10$ edges in $K_5$, hence:
(3)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:
- 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:
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:

There are $6$ vertices and $9$ edges in $K_{3,3}$. Applying Lemma 2 we get that:
(6)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:
- 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:
Note that we can verify this general formula to be true for Lemmas 1 and 2. Suppose $g = 3$, then it follows that:
(9)We can also verify this for $g = 4$:
(10)