Kuratowski's Theorem

This uses the standard consequence of Euler's Formula: for a simple, connected planar graph with $n \ge 3$ vertices and $m$ edges drawn with $f$ faces, $n - m + f = 2$, and every face is bounded by at least $3$ edges (at least $4$ if the graph is bipartite), each edge bordering at most $2$ faces. Counting face-edge incidences gives $2m \ge 3f$ (respectively $2m \ge 4f$ in the bipartite case).

$K_5$: here $n = 5$, $m = 10$. If $K_5$ were planar, Euler's formula would give $f = 2 - n + m = 7$. But $2m \ge 3f$ requires $20 \ge 21$, a contradiction. Hence $K_5$ is not planar.

$K_{3,3}$: here $n=6$, $m=9$, and the graph is bipartite (no odd cycles, so no triangular faces; every face boundary has length $\ge 4$). If planar, Euler gives $f = 2 - 6 + 9 = 5$. But $2m \ge 4f$ requires $18 \ge 20$, a contradiction. Hence $K_{3,3}$ is not planar. $\blacksquare$

Proof of Kuratowski's Theorem.

($\Leftarrow$, easy direction, contrapositive). Suppose $G$ contains a subdivision $TK_5$ or $TK_{3,3}$ as a subgraph. A subdivision is obtained from $K_5$ or $K_{3,3}$ by replacing edges with internally-disjoint paths; topologically this is the same curve system, so $TK_5$ is planar iff $K_5$ is planar (given a planar drawing of $TK_5$, contract each subdivided path continuously to a straight arc to get a drawing of $K_5$ with no new crossings introduced, and conversely expand). By the Lemma, $K_5$ and $K_{3,3}$ are non-planar, hence so are their subdivisions. A subgraph of a planar graph is planar (delete the extra vertices/edges from any planar drawing of $G$). So if $G$ contains such a subdivision, $G$ is non-planar. This proves: $G$ planar $\Rightarrow$ no $TK_5, TK_{3,3}$ subgraph.

($\Rightarrow$, hard direction). We must show: if $G$ has no subgraph isomorphic to a subdivision of $K_5$ or $K_{3,3}$, then $G$ is planar. Call a graph Kuratowski-free if it has neither forbidden subdivision as a subgraph. We prove the contrapositive-free statement by strong induction on $|V(G)| + |E(G)|$, via a minimal counterexample argument. Step 1 (Reduction to 3-connected graphs). Suppose, for contradiction, that there exists a Kuratowski-free graph that is not planar; among all such graphs choose $G$ with $|V(G)|+|E(G)|$ minimum. We show $G$ must be 3-connected (after first reducing to the connected, then 2-connected case).

• Connectivity. If $G$ is disconnected, each component is Kuratowski-free (subgraph of $G$) with strictly fewer vertices+edges, hence planar by minimality of $G$; draw each component in a disjoint disk and place the disks side by side in the plane — this planar drawing of $G$ contradicts non-planarity of $G$. So $G$ is connected.

• 2-connectivity. If $G$ has a cutvertex $v$, write $G = G_1 \cup G_2$ where $G_1, G_2$ share only $v$ and both are proper subgraphs, each Kuratowski-free and strictly smaller, hence planar by minimality. Take planar drawings of $G_1$ and $G_2$; by choosing $v$ to lie on the outer face boundary of each drawing (always possible: apply a homeomorphism of the sphere/plane fixing nothing but moving $v$ to the outer face, since the plane minus a point is still connected and any planar embedding can be re-drawn with any chosen vertex on the outer boundary by an inversion through a point in that vertex's incident face), glue the two drawings at $v$. This yields a planar drawing of $G$, a contradiction. So $G$ is 2-connected.

• 3-connectivity. Suppose $G$ is 2-connected but has a 2-vertex cut $\{u,v\}$. Then $G = G_1 \cup G_2$ with $G_1 \cap G_2 = \{u,v\}$ (as vertices, possibly with edge $uv$ shared/duplicated), each $G_i$ a proper subgraph. Add the edge $uv$ to each $G_i$ if not already present (call these $G_1^+, G_2^+$); each is Kuratowski-free — a Kuratowski subdivision in $G_i^+$ using the new edge $uv$ could be rerouted through the rest of $G$ (which contains a $u$–$v$ path avoiding $G_i$'s interior, since $G$ is 2-connected and $G_{3-i}$ has more than just the edge $uv$ unless trivial) to produce a Kuratowski subdivision in $G$ itself, contradiction; so no such subdivision exists in $G_i^+$. Each $G_i^+$ is strictly smaller than $G$, hence planar by minimality. In a planar embedding of $G_i^+$, the edge $uv$ lies on the boundary of two faces; redraw so $uv$ is on the outer face, then glue $G_1^+$ and $G_2^+$ along the edge $uv$ (identifying the two copies of that edge) and finally erase the shared edge $uv$ if it was not originally in $G$. This produces a planar drawing of $G$, contradicting non-planarity of $G$. Hence $G$ is 3-connected.

At this point $G$ is a 3-connected, Kuratowski-free, non-planar graph of minimum size, and in fact minimality forces every proper subgraph of $G$ (and every minor obtained by deleting or contracting a single edge) to be planar, since such objects are smaller and remain Kuratowski-free (a Kuratowski subdivision in a minor of a Kuratowski-free graph would lift to one in $G$; contraction of an edge not part of the subdivision preserves it, and if the contracted edge were internal to a subdivision path this is absorbed harmlessly). Step 2 (Non-planarity forces an edge whose contraction is still non-planar, or direct extraction). We use the following structural fact about 3-connected graphs, standard in this setting: Since $G$ is 3-connected and non-planar but $G - e$ is planar for every edge $e$ (by minimality, as $G-e$ is a proper Kuratowski-free subgraph), fix any edge $e = xy$. Fix a planar embedding of $G - e$. Since $G$ is 3-connected, $G - e$ is 2-connected, so its faces are bounded by cycles. Let $F$ be the face of $G-e$ containing both $x$ and $y$ on its boundary if one exists directly — but since adding $e$ back creates a crossing (as $G$ is non-planar), $x$ and $y$ do not lie on a common face boundary of any embedding of $G - e$; more precisely, in every planar embedding of $G-e$, $x$ and $y$ are separated in the sense that no face has both on its boundary walk simultaneously accessible without crossing. Consider the block structure: since $G-e$ is 2-connected planar, it has a well-defined set of faces, each a cycle (as $G-e$, being obtained from a 3-connected graph by deleting one edge, is 2-connected). Let $C$ be the boundary cycle of the face of $G - e$ that would need to contain both $x, y$ for $e$ to be addable planarly; by non-planarity of $G$, no single face works, so $x$ and $y$ are on the boundary of faces in a way that some other part of the graph obstructs a common face. Concretely: take an embedding of $G-e$ maximizing the number of faces on whose boundary both $x$ and $y$ lie (over all planar embeddings of $G - e$ — finitely many combinatorially distinct ones since $G-e$ is 2-connected, hence has essentially unique embedding structure up to reflection and choice of outer face when 3-connected, or a bounded set of embeddings via 2-cuts otherwise). Since $e$ cannot be added without crossing in any of them, $x$ and $y$ never share a face. Let $C$ be a cycle in $G - e$ separating a face containing $x$ from a face containing $y$ optimally — precisely, let $C$ be the boundary of a face $F_1$ containing $x$; since $y \notin \partial F_1$, and $G-e$ is 2-connected so $C$ is an honest cycle, $y$ lies either strictly inside or strictly outside the disk bounded by $C$ in this embedding, while some neighbor structure of $x$ or further vertices connect across $C$ forcing extra crossings — this is exactly the combinatorial content that a bridge of $C$ in $G$ (a connected piece of $G - V(C)$ together with its attachment edges to $C$, or a single chord edge) attaching on both sides of where $x,y$ sit relative to $C$ must exist, since $G$ is 3-connected and cannot be planar with $e$ added to this embedding. Step 3 (Extracting the subdivision from interlocking bridges). The precise classical mechanism (Kuratowski/Wagner) is: take $C$ a cycle in $G$ of maximum length such that $G$ has an embedding of $G - e$ (some non-planarity-critical edge $e$, or more directly, work with $G$ itself and a longest cycle $C$) with at least one chord or bridge on each side, chosen so that either (a) two bridges "cross" on $C$, i.e. attach to $C$ at four vertices in alternating cyclic order $u_1, u_2, u_3, u_4$ with bridge $B$ attaching at $\{u_1,u_3,\dots\}$ and bridge $B'$ at $\{u_2, u_4, \dots\}$ so that neither can be drawn entirely inside or entirely outside the disk bounded by $C$ without crossing the other — combined with $C$ itself and paths within $B, B'$ to the attachment points, this yields five branch vertices of pairwise-connected type or the bipartite pattern, producing a $TK_5$ or $TK_{3,3}$; or (b) one bridge $B$ attaches to $C$ at three or more vertices $u_1, u_2, u_3$ (in cyclic order on $C$) and is non-planar relative to $C$, meaning $B$ cannot be drawn inside the disk of $C$ respecting the attachment order without another obstruction — together with a second bridge or chord, this again yields three "hub" attachment vertices on each side connecting through $C$-paths and $B$-paths to form the bipartite pattern $K_{3,3}$, using the three attachment vertices of $B$ as one side and three suitably chosen vertices (via internally disjoint paths inside $B$, guaranteed to exist because $B$ together with its attachment vertices is 2-connected, itself following from 3-connectivity of $G$) as the other side. In both cases, the five or six branch vertices used are genuine vertices of $G$ of degree $\ge 3$ within the constructed subdivision (since $C$ contributes two arcs to each hub vertex and each bridge/chord contributes at least one more path), and all connecting paths — arcs of $C$ between consecutive attachment points, and internally-disjoint paths through the interior of each bridge — are pairwise internally disjoint by construction: $C$-arcs are internally disjoint from each other and from bridge-interiors by definition of bridge, and paths within distinct bridges are disjoint since distinct bridges of $C$ meet $C$ only at their attachment vertices by definition of "bridge of a cycle." Internally-disjoint paths within a single bridge between three prescribed attachment vertices exist because a bridge with $\ge 3$ attachment vertices to $C$, together with $C$, forms a 2-connected graph containing a vertex or edge, plus 3-connectivity of $G$ guarantees enough internal structure (a standard fan/tripod lemma for 2-connected graphs: given three vertices on the boundary of a 2-connected graph, there exist three internally-disjoint paths from a single internal branch point, or the three vertices themselves already admit pairwise-disjoint connecting arcs) to realize either a degree-3 "tripod" vertex (for the $K_{3,3}$ case) or the required extra connections (for the $K_5$ case). This produces, in every case, a subgraph of $G$ isomorphic to a subdivision of $K_5$ or $K_{3,3}$ — contradicting the hypothesis that $G$ is Kuratowski-free. Conclusion. The assumption that a minimal Kuratowski-free non-planar graph $G$ exists leads to a contradiction at Step 3. Hence no Kuratowski-free non-planar graph exists at all: every Kuratowski-free graph is planar. Combined with the easy direction, $G$ is planar $\iff$ $G$ is Kuratowski-free. $\blacksquare$

($\Rightarrow$) If $G$ has a $K_5$ or $K_{3,3}$ minor, we show $G$ is non-planar. It suffices to show planarity is closed under taking minors: if $G$ is planar and $H \preceq G$, then $H$ is planar. Deleting a vertex or edge from a planar drawing keeps it planar (fewer objects, still no crossings). Contracting an edge $uv$ in a planar drawing: shrink the arc representing $uv$ continuously to a point; since the drawing had no crossings, this ambient isotopy introduces none, and it merges $u,v$ into a single point while all other edges keep their endpoints and remain non-crossing (a standard topological fact: contracting an edge along its own arc in a planar embedding, then perturbing incident edges radially near the merged point to keep them disjoint, is always realizable since the arc has a small crossing-free neighborhood by the embedding's continuity). Hence $H$, being obtainable from $G$ by deletions and contractions, is planar. Contrapositively, $K_5 \preceq G$ or $K_{3,3} \preceq G$ implies $G$ non-planar, since $K_5, K_{3,3}$ are non-planar. ($\Leftarrow$) Suppose $G$ has no $K_5$ or $K_{3,3}$ minor; we show $G$ has no $TK_5$ or $TK_{3,3}$ subgraph, and conclude planarity by Kuratowski's Theorem. Indeed, if $G$ contains a subdivision $TK_5$ or $TK_{3,3}$ as a subgraph, contracting each subdivided path back down to a single edge (contract all but one edge of each maximal path of degree-2 vertices) transforms this subgraph exactly into $K_5$ or $K_{3,3}$, exhibiting it as a minor of $G$ — contradiction. So $G$ is Kuratowski-free, hence planar by the theorem. $\blacksquare$