Kuratowski's Theorem

From ProofWiki
Jump to: navigation, search

Theorem

The following conditions on a graph $\Gamma$ are equivalent:

$(1): \quad \Gamma$ is planar
$(2): \quad \Gamma$ contains no subdivision of either the complete graph $K_5$ or the complete bipartite graph $K_{3, 3}$.


Proof

Let $\Gamma$ be a graph with $V$ vertices, $E$ edges and $F$ faces.


The proof proceeds in two parts: $(1) \implies (2)$ and $(2) \implies (1)$.


$(1)$ implies $(2)$

First we consider $K_5$.

$K_5$ has $5$ vertices and $10$ edges.

By the Euler Polyhedron Formula, a planar embedding would have $7$ faces.

But each face has at least $3$ edges, while each edge bounds at most two faces.

Suppose we count the incident edge-face pairs.

Then the number of faces is at most:

$E \dfrac 2 3 = 6 \dfrac 2 3$

which contradicts the deduction that $K_5$, if planar, should have $7$ faces.

Hence $K_5$ is non-planar.


Now consider $K_{3, 3}$.

$K_{3, 3}$ has $6$ vertices and $9$ edges.

Hence $K_{3, 3}$ has $5$ faces if it is planar.

Since $K_{3, 3}$ is bipartite, from Graph is Bipartite iff No Odd Cycles, each cycle in $K_{3,3}$ has an even number of edges.

Hence any face must have at least $4$ edges.

So the number of faces is at most

$E \dfrac 2 4 = 4 \dfrac 1 2$

which contradicts the deduction that $K_{3, 3}$, if planar, should have $5$ faces.

Hence $K_{3, 3}$ is non-planar.


Now consider a subdivision of either graph.

The arguments as above continue to work as before, since both $V$ and $E$ have increased by one in the Euler formula.

So the expected value of $F$ is unchanged.


Hence if a graph $\Gamma$ contains a subdivision of $K_5$ or $K_{3,3}$, then $\Gamma$ is not planar.

Taking the contrapositive:

$\Gamma$ is a planar graph $\implies \Gamma$ does not contain a subdivision of either $K_5$ or $K_{3, 3}$.


$(2)$ implies $(1)$


Source of Name

This entry was named for Kazimierz Kuratowski.