Why can't we use $E \le 3V - 6$ to prove that $K_{3,3}$ is nonplanar?

Question

So our course notes used the inequality that $E \le 3V - 6$ to prove that $K_5$ is nonplanar. I know that to prove $K_{3,3}$ is nonplanar, we use a different inequality. My question is why we can't use the same inequality for $K_{3,3}$?

Answer 1

Because $K_{3,3}$ satisfies the inequality, despite being nonplanar.

It has $9$ edges and $6$ vertices, and in fact $9 \leq 3\cdot6 - 6 = 12$.

Answer 2

There is a generalization to $E\leq 3V-6$ which works:

Using a double counting we get: $\sum_{f}|f|=2E$ (the sum over each face of the number of edges)

So if each face has at least $k$ edges you get $kF\geq 2E$ or $F\geq \frac{2E}{k}$

Plugging into Euler's formula yields:

$V-E+\frac{2E}{k}\geq 2 \implies \frac{k-2}{k}E\leq V-2\implies E\leq (V-2)\frac{k}{k-2}$.

The inequality you are using is the case when $k=3$.

Of course a bipartite graph has no odd cycles, so we can use the version with $k=4$, and that one is strong enough to finish the problem.