(related to Problem: Checking if $K_{3,3}$ is Planar)

- Suppose that the complete bipartite graph $K_{3,3}$ is planar is planar.
- Note that the shortest cycle in $K_{3,3}$ is of length $4.$
- A necessary condition for a graph to be planar with shortest cycle requires that $$|E|\le \frac{k}{k-2}(|V|-2),$$ where $|E|$ ist the number of its edges and $|V|$ is the number of its vertices.
- For $K_{3,3}$ this condition means that $$|E|=9\le \frac{4}{2}(6-2)=2\cdot 4=8.$$ which is false.
- Therefore, $K_{3,3}$ is not planar.

**Aldous Joan M., Wilson Robin J.**: "Graphs and Applications - An Introductory Approach", Springer, 2000