---
tag: 030A3FHN14
kind: statement
role: proposition
name: K5 and K3,3 are not planar
msc: [05C10]
uses: [03WKB2H474, 0V0GC7BQAN, 029JQEK15B, 0SM1REAVYJ]
sources:
  - url: https://en.wikipedia.org/wiki/Three_utilities_problem
    locator: Unsolvability
---

## Statement

The [[complete graph|03WKB2H474]] $K_5$ and the [[complete bipartite graph|0V0GC7BQAN]] $K_{3,3}$ are not [[planar|029JQEK15B]].

## Remarks

The graph $K_5$ has $5$ vertices and $10$ edges. The [[edge bound for planar graphs|0SM1REAVYJ]] allows at most $3 \cdot 5 - 6 = 9$ edges.
The graph $K_{3,3}$ has $6$ vertices and $9$ edges, and it has no cycle of length $3$. The bound $e \le 2v - 4$ allows at most $8$ edges.
The statement for $K_{3,3}$ is the three utilities problem: three houses cannot each be joined to three utilities without crossings.

## Explanations

### L1 human

Try to join each of three houses to each of three utilities with lines that never cross.
It is impossible, and the reason is a count of edges and faces.