Planar complete graphs

We will derive a necessary inequality for planar graphs ( $E \leq 3n - 6$ ), then show the inequality does not hold for $K_5$ and $K_6$ . ( $K_4$ is easily shown to be planar by sketching it.) Below, we will use $n$ , $E$ , and $F$ to denote the number of vertices, edges, and faces, respectively.

Consider $K_n$ , a complete graph with $n > 2$ vertices (and hence $E \geq 3$ ). To be fully enclosed, each face must be at least a triangle. So, at least 3 edges bound each face. To relate faces with edges, note that $3F$ will double-count the minimum number of edges, since each edge has two sides and hence bounds two faces. So, we must divide this count by two: $E \geq 3F/2$ , or $F \leq 2E/3$ .

Euler's formula holds for any planar graph: $n - E + F = 2$ . Substituting the above inequality into Euler's formula: $F = 2 - n + E \leq 2E/3$ .

Hence, a planar graph with $n > 2$ and $E \geq 3$ implies that $E \leq 3n - 6$ .

Now, using this condition, let's see if $K_4$ , $K_5$ , and $K_6$ are planar. We know that the number of edges in $K_n$ is $\dbinom{n}{2} = n(n-1)/2$ . So:

• $K_4$ is planar , since we can easily draw by hand a planar graph with four vertices where each is connected to the others. Note that the inequality above is true for all planar graphs, including $K_4$ . But, it may also hold for non-planar graphs, so the inequality is not proof by itself that $K_4$ is planar.

• $K_5$ : $n = 5, E_5 = \dbinom{5}{2} = 10$ . Is it planar? $E_5 \gt 3 \cdot 5 - 6$ , so $K_5$ cannot be planar .

• $K_6$ : $n = 6, E_6 = \dbinom{6}{2} = 15$ . Is it planar? $E_6 \gt 3 \cdot 6 - 6$ , so $K_6$ cannot be planar .