Proof that K5 and K3,3 are not planar

Proof

We use the edge bound for $K_5$, and Euler's formula with a face count for $K_{3,3}$.

The graph $K_5$.

1. The complete graph $K_5$ is simple, and it is connected because any two distinct vertices are adjacent.
2. It has $v = 5$ vertices and, by the number of edges of a complete graph, $e = \binom{5}{2} = 10$ edges.
3. Suppose that $K_5$ is planar. Since $v = 5 \ge 3$, the edge bound for planar graphs gives $e \le 3 \cdot 5 - 6 = 9$.
4. This contradicts $e = 10$. So $K_5$ is not planar.

The graph $K_{3,3}$.

5. Let the complete bipartite graph $K_{3,3}$ have parts $A$ and $B$ with $\abs{A} = \abs{B} = 3$. It has $v = 6$ vertices and $e = 3 \cdot 3 = 9$ edges, one for each pair in $A \times B$.
6. It is connected. Two vertices in different parts are adjacent. Two vertices in the same part have a common neighbour in the other part.
7. Suppose that $K_{3,3}$ is planar, and fix a drawing with no crossings. Let $f$ be its number of faces.
8. By Euler's formula, $f = 2 - v + e = 2 - 6 + 9 = 5$.
9. For a face $F$, let $\ell(F)$ be the number of edge sides that border $F$, where an edge with $F$ on both sides counts twice. Each edge has two sides, and each side borders exactly one face. So $\sum_F \ell(F) = 2e = 18$.
10. The boundary of each face $F$ is traced by a closed walk of length $\ell(F)$, since the graph is connected and has an edge.
11. The graph $K_{3,3}$ is bipartite. Each step of a walk moves between $A$ and $B$, so a closed walk takes an even number of steps. Thus each $\ell(F)$ is even.
12. Each face borders some edge side, as the graph is connected with an edge, so $\ell(F) \ge 1$. A simple graph has no two edges with the same ends. So a boundary walk of length $2$ goes along one edge $xy$ and straight back. This happens only when $x$ and $y$ both have degree $1$. In $K_{3,3}$ every vertex has degree $3$, so this does not happen.
13. By Steps 11 and 12, $\ell(F) \ge 4$ for every face $F$. Hence $4f \le 18$ by Step 9.
14. By Step 8, $4f = 20 > 18$. This contradiction shows that $K_{3,3}$ is not planar.