= Kuratowski's theorem
{c}
{wiki}
A finite <simple graph> is a <planar graph> if and only if it contains no <graph subdivision> of the <complete graph> $K_5$ or the <complete bipartite graph> $K_{3,3}$ as a <subgraph>; equivalently, neither is a <topological minor>. The easy direction follows by tracing each replacement <graph path> as one drawn <edge>. The converse asserts that every failure of planarity contains one of these two patterns.<Graph Theory by Reinhard Diestel/Planar Graphs (author-hosted chapter preview)>[§4.4, Theorem 4.4.6(iii), printed p. 111]{ref}
<Graph Theory by Reinhard Diestel> (Planar Graphs preview, §4.4, Theorem 4.4.6, printed p. 111) dates <Kuratowski's theorem> to 1930 and the equivalent <graph minor> characterization to 1937. These dates are that textbook's historical attribution.
Back to article page
