Kuratowski's theorem

Theorem

Kuratowski's theorem

T-112Home MU-307Threads structure · number

Statement

Let \(G\) be a finite simple graph. Then \(G\) is planar (admits an embedding in the plane with no crossing edges) if and only if \(G\) contains no subgraph that is a subdivision of \(K_5\) (the complete graph on 5 vertices) or of \(K_{3,3}\) (the complete bipartite graph on parts of size 3). Equivalently: \(G\) is non-planar exactly when it contains a subdivision of \(K_5\) or of \(K_{3,3}\) as a subgraph.

Why it matters

Kuratowski's theorem converts a topological question — "can this graph be drawn in the plane without crossings?" — into a finite, purely combinatorial obstruction: the presence or absence of two specific small patterns. It is the prototype for an entire style of theorem in graph theory (Wagner's minor-version restatement, and ultimately the Robertson–Seymour graph minor theorem, which shows every minor-closed graph property has a finite obstruction set, exactly as planarity does here with two graphs).

It also underlies practical graph algorithms: planarity testing, circuit layout on a single board layer, and map/graph drawing all reduce, in principle, to searching for a \(K_5\)- or \(K_{3,3}\)-subdivision, even though the efficient linear-time algorithms (Hopcroft–Tarjan and successors) avoid a literal search by other means.

Hypotheses

\(G\) is finite.The theorem is stated and proved for graphs with finitely many vertices and edges. For infinite graphs the situation is more delicate: naive extensions of the Kuratowski criterion fail, and a correct infinite analogue (Halin, and later the full topological classification for infinite graphs) requires allowing subdivisions with infinitely many branch vertices and additional end-space considerations that have no finite counterpart.

\(G\) is simple (no loops or parallel edges).This is a convenience, not a real restriction: loops and multi-edges never participate in a \(K_5\)- or \(K_{3,3}\)-subdivision (those have simple underlying graphs), and deleting loops/merging parallel edges changes neither planarity nor the presence of such a subdivision, so the simple case decides the general case for free.

The forbidden objects must be subdivisions (topological minors), not literal subgraphs.If one instead asked "does \(G\) contain \(K_5\) or \(K_{3,3}\) as an exact subgraph on 5 or 6 vertices", the criterion would be wrong: take \(K_5\) and replace one edge by a path of length 2. The resulting 6-vertex graph contains no \(K_5\) subgraph and no \(K_{3,3}\) subgraph at all, yet it is still non-planar (it is homeomorphic to \(K_5\)).

Both forbidden graphs are needed; neither one alone suffices.\(K_{3,3}\) itself contains no subdivision of \(K_5\) (its maximum degree is 3, but every branch vertex of a \(K_5\)-subdivision needs degree \(\geq 4\)), yet \(K_{3,3}\) is non-planar. Symmetrically \(K_5\) contains no \(K_{3,3}\)-subdivision. So a one-graph criterion using either alone is false.

Proof

\text{A } subdivision \text{ of a graph } H \text{ is any graph obtained from } H \text{ by replacing each edge } uv \text{ of } H \text{ by a path } P_{uv} \text{ with new internal vertices of degree 2, all internally disjoint.}

Definition, fixed for the rest of the proof; vertices of \(H\) surviving in the subdivision are the branch vertices.A

\text{(Euler's formula) If } G \text{ is a connected simple planar graph with } n\geq 3 \text{ vertices and } m \text{ edges, embedded with } f \text{ faces, then } n-m+f=2.

Cited as a standard lemma (proved by induction on \(m\): true for a spanning tree with \(f=1\), and each extra edge closing a cycle adds exactly one face).A

m \le 3n-6, \qquad \text{and, if } G \text{ is triangle-free (in particular bipartite), } m \le 2n-4.

Each face is bounded by \(\geq 3\) edges (\(\geq 4\) if triangle-free), and each edge borders exactly 2 faces, so \(2m\ge 3f\) (resp. \(2m \ge 4f\)); substitute \(f\ge \tfrac{2m}{3}\) (resp. \(\tfrac{m}{2}\)) into Step 2 and solve for \(m\).A

K_5 \text{ and } K_{3,3} \text{ are non-planar.}

\(K_5\) has \(n=5,\,m=10\), and \(3n-6=9\lt 10\), contradicting Step 3. \(K_{3,3}\) is bipartite with \(n=6,\,m=9\), and \(2n-4=8\lt 9\), contradicting the triangle-free bound of Step 3.B

\text{Planarity is closed under taking subgraphs and under "un-subdividing": } G \text{ planar} \implies \text{every subgraph of } G \text{ planar, and } G \text{ planar} \iff \text{any subdivision of } G \text{ planar.}

Delete edges/vertices from a plane drawing to get a plane drawing of the subgraph; replacing an edge by a path drawn along a curve arbitrarily close to that edge (or contracting internal degree-2 vertices back into an edge) does not create or remove crossings.A

\text{If } G \text{ contains a subdivision of } K_5 \text{ or } K_{3,3} \text{, then } G \text{ is non-planar.}

By Step 4, \(K_5,K_{3,3}\) are non-planar; by Step 5 their subdivisions are non-planar; a graph containing a non-planar subgraph is itself non-planar (Step 5, subgraph closure, contrapositive). This proves the "only if" direction of the theorem.A

\text{Now the hard direction. Suppose, for contradiction, that some finite simple graph is non-planar but contains no } K_5\text{- or } K_{3,3}\text{-subdivision. Let } G \text{ be such a graph with } |V(G)|+|E(G)| \text{ minimum.}

Minimal-counterexample setup; \(G\) is well-defined since the class of counterexamples, if non-empty, has a minimum-size member (finite graphs).B

G \text{ is 2-connected.}

If \(G\) is disconnected or has a cut vertex, split it into two proper subgraphs \(G_1,G_2\) overlapping in at most one vertex with \(G=G_1\cup G_2\). Each \(G_i\) is smaller than \(G\) and inherits "no \(K_5/K_{3,3}\)-subdivision" (Step 5, subgraph closure of the forbidden pattern), so by minimality of \(G\) each \(G_i\) is planar. Two plane drawings sharing at most one vertex can be glued at that vertex (translate/scale one drawing so the shared vertex coincides and the drawings occupy disjoint regions) to planarly embed \(G\), contradicting non-planarity of \(G\).C

G \text{ is 3-connected.}

If \(G\) is 2-connected but has a 2-vertex cut \(\{x,y\}\), write \(G=G_1\cup G_2\) with \(V(G_1)\cap V(G_2)=\{x,y\}\), each \(G_i\) smaller than \(G\), hence planar by minimality (as in Step 8). Add the edge \(xy\) to each \(G_i\) if not already present (this can only help realize a subdivision, so each \(G_i+xy\) is still \(K_5/K_{3,3}\)-subdivision-free, hence planar by minimality, since \(|G_i+xy|\lt |G|\)). In a plane drawing of a 2-connected planar graph, \(x\) and \(y\) lie on a common face boundary (they are joined by an edge or, after adding one, are on a common face), so the two drawings can be glued along the segment/curve representing \(xy\) and that edge then erased, yielding a plane drawing of \(G\) — contradiction.C

\text{Fix any edge } e=xy \text{ of } G, \text{ and set } G'=G-e.

\(G\) is 3-connected (Step 9) and simple, so \(G\) has at least one edge (indeed \(\ge 4\) vertices, \(\ge 6\) edges); \(G'\) has fewer edges than \(G\) and no \(K_5/K_{3,3}\)-subdivision (subgraph of \(G\)), so by minimality of \(G\), \(G'\) is planar. Fix a plane embedding of \(G'\).B

\text{Every face of this embedding of } G' \text{ is bounded by a cycle.}

Removing one edge from a 3-connected graph leaves a 2-connected graph (a graph is \(k\)-connected iff removing any \(k-1\) vertices leaves it connected; deleting an edge cannot lower connectivity below \(k-1\)... concretely: any 2-vertex cut of \(G'\) together with one more vertex would be a 3-vertex separation of \(G\) unless it already separated \(G\), and 3-connectivity of \(G\) rules that out). Standard lemma: in a 2-connected plane graph every face is bounded by a cycle (no cut vertices to pinch a face boundary into a non-cyclic closed walk).C

\text{If some face of the fixed embedding of } G' \text{ has } x \text{ and } y \text{ both on its boundary cycle, } G \text{ is planar — contradiction.}

Draw \(e=xy\) as a new curve through the interior of that face, joining \(x\) to \(y\) without crossing any existing edge (possible since both lie on the boundary of one common face). This is a plane embedding of \(G'+e=G\), contradicting the non-planarity of \(G\).B

\text{So no face boundary contains both } x \text{ and } y. \text{ This forces } G \text{ to contain a subdivision of } K_5 \text{ or } K_{3,3} \text{ after all — contradicting the choice of } G.

This is the technical heart of the classical proof (Kuratowski 1930; the version above follows the bridge/face argument in Diestel's Graph Theory, cited here as an established Lemma rather than re-derived line by line): choose a face \(F\) of the embedding of \(G'\) whose boundary cycle \(C\) separates \(x\) and \(y\) as far as possible, and analyse the "bridges" of \(C\) in \(G'\) (the components of \(G'-V(C)\) together with their attachment edges to \(C\), plus chords of \(C\)). Since \(x,y\) never share a face, some bridge must attach to \(C\) in a pattern that "interleaves" around \(x\) and \(y\); a case analysis on how many attachment vertices such a bridge has, and on whether two bridges attach in overlapping or nested arcs of \(C\), produces in every case either five branch vertices pairwise linked by internally disjoint paths (a \(K_5\)-subdivision) or two triples of branch vertices completely cross-linked (a \(K_{3,3}\)-subdivision), using the edge \(xy\) itself as one of the required connecting paths.C

\text{No minimal counterexample } G \text{ exists; hence every finite simple graph with no } K_5\text{- or } K_{3,3}\text{-subdivision is planar.}

Steps 7–13 derive a contradiction from the mere existence of a minimal counterexample. Combined with Step 6, this establishes both directions of the theorem.A

Result

G \text{ planar} \iff G \text{ contains no subdivision of } K_5 \text{ or } K_{3,3}

Reading. You can draw a graph in the plane without any edges crossing precisely when it does not secretly contain, as a "stretched-out" copy sitting inside it, either of the two smallest genuinely non-planar patterns: five mutually joined vertices, or two groups of three vertices each fully joined across the groups.

Scope. Applies to arbitrary finite simple graphs (multigraphs and loops reduce to the simple case, Hypotheses). Does not directly extend to infinite graphs without modification. The criterion is an exact structural characterisation, not merely a necessary condition like Euler's edge bound.

Corollaries & converses

Wagner's theorem (minor form): \(G\) is planar iff it has no \(K_5\) or \(K_{3,3}\) minor. This is genuinely equivalent to Kuratowski's subdivision form for these two specific graphs (though "subdivision" and "minor" differ for general \(H\)); the equivalence needs a separate short argument showing any \(K_5\)- or \(K_{3,3}\)-minor can be "uncontracted" back into a subdivision.
Every edge-maximal planar graph on \(n\ge 3\) vertices is a triangulation with exactly \(3n-6\) edges (equality case of Step 3), and Kuratowski's theorem certifies that adding any further edge to it must create a \(K_5\)- or \(K_{3,3}\)-subdivision.
The statement is a genuine "if and only if": both directions were proved above (Step 6 for one direction, Steps 7–14 for the other), so there is no separate converse to check — the theorem already is its own converse pairing.
Consequence for testing: to prove a specific graph non-planar it suffices to exhibit one \(K_5\)- or \(K_{3,3}\)-subdivision inside it; to prove planarity via this theorem one must instead argue the total absence of such a subdivision, which is generally harder by hand (efficient algorithms avoid this by other means).

Fails without

Restricting to only one forbidden graph: \(K_{3,3}\) contains no \(K_5\)-subdivision (its branch vertices would need degree \(\ge 4\), but \(K_{3,3}\) is 3-regular) yet is non-planar, so "no \(K_5\)-subdivision" alone does not imply planar.
Using exact subgraphs instead of subdivisions: take \(K_5\) and subdivide one edge once (insert a degree-2 vertex on it). The result has 6 vertices and no 5- or 6-vertex subgraph isomorphic to \(K_5\) or \(K_{3,3}\), yet it is non-planar (homeomorphic to \(K_5\)) — the "exact subgraph" criterion wrongly certifies it planar.
Dropping finiteness: for infinite graphs, a locally finite tree-like structure can be non-planar in a way not captured by any finite subdivision of \(K_5\) or \(K_{3,3}\) sitting inside it (the obstruction can only be witnessed "in the limit"), so the naive infinite restatement of the theorem is false without extra topological hypotheses on the ends of the graph.

Common errors

Checking only for \(K_5\) or \(K_{3,3}\) as literal subgraphs, missing subdivided (stretched) copies — the single most common mistake.
Checking only one of the two graphs and stopping, e.g. concluding "no \(K_5\) found, so planar" without also ruling out \(K_{3,3}\).
Using the edge bound \(m\le 3n-6\) as if it were equivalent to Kuratowski's criterion; the bound is necessary but not sufficient (e.g. subdivided \(K_5\) can easily satisfy \(m \le 3n-6\) while still being non-planar).
Applying the triangle-free bound \(m\le 2n-4\) to a graph that is not actually triangle-free.
Assuming a \(K_5\)- or \(K_{3,3}\)-minor automatically hands you a subdivision without checking degrees; this is fine for \(K_5\) and \(K_{3,3}\) by Wagner's equivalence but is false for topological minors of general graphs \(H\) with a vertex of degree \(\ge 5\).
Forgetting that subdivision paths must be internally vertex-disjoint (reusing a "branch" vertex or path interior for two different connections does not produce a valid subdivision).

Discussion

Kazimierz Kuratowski published the theorem in 1930; the same result was found independently at almost the same time by Orrin Frink and Paul Smith (unpublished) and by Lev Pontryagin. Klaus Wagner gave the minor-graph reformulation in 1937, which turned out to be the historically more productive phrasing: it is the first non-trivial instance of a finite forbidden-minor characterisation of a graph property.

The deepest modern descendant of this idea is the Robertson–Seymour graph minor theorem (proved across a two-decade series of papers), which shows that every graph property closed under taking minors — planarity is one instance — is characterised by a finite list of forbidden minors, even though no general algorithm produces that list. Kuratowski's theorem is the case that started the programme, with the list explicitly known and of size two.

Algorithmically, the theorem is a certificate, not a test: it tells you what a witness of non-planarity looks like, but literally hunting for a \(K_5\)/\(K_{3,3}\)-subdivision by brute force is not how planarity is decided in practice. Linear-time algorithms (Hopcroft–Tarjan 1974, and the simpler left-right or PQ-tree methods since) test planarity directly via depth-first search structure, and only invoke a Kuratowski-subgraph extraction as a separate, slower post-processing step when a human-readable certificate of non-planarity is wanted.

A frequent misconception is treating "subdivision" and "minor" as always interchangeable because they happen to coincide for \(K_5\) and \(K_{3,3}\). In general a graph \(H\) can appear as a minor of \(G\) without appearing as a topological minor (subdivision) of \(G\), specifically when \(H\) has a vertex of degree \(\ge 5\) — branch vertices of a subdivision are constrained to have degree exactly \(\deg_H(v)\) at that point of \(G\), which forces \(G\) itself to have a vertex of degree \(\ge 5\) there, whereas contraction (minors) has no such local degree obstruction. The coincidence for Kuratowski's two graphs (max degree 4 and 3 respectively) is part of what makes them the clean minimal case.

Worked examples

\text{Show the Petersen graph is non-planar by exhibiting a } K_{3,3}\text{-subdivision.}

Petersen graph: outer 5-cycle \(o_0o_1o_2o_3o_4\), inner 5-cycle (pentagram) with edges \(i_ji_{j+2\bmod 5}\), and spokes \(o_ji_j\); every vertex has degree 3, so a \(K_5\)-subdivision (needing degree-4 branch vertices) is impossible here, but a \(K_{3,3}\)-subdivision (degree 3 exactly) is plausible.B

\text{Take branch sets } A=\{o_0,o_2,i_1\}, \ B=\{o_1,i_3,i_4\}.

Candidate partition into the two sides of \(K_{3,3}\); need 9 internally disjoint paths, one for each pair \((a,b)\in A\times B\), using only the 4 leftover vertices \(\{o_3,o_4,i_0,i_2\}\) as internal points.A

o_0\!-\!o_1,\quad o_0\!-\!i_0\!-\!i_3,\quad o_0\!-\!o_4\!-\!i_4

All three edges at \(o_0\) (namely \(o_0o_1,\,o_0i_0,\,o_0o_4\)) are used exactly once each, and \(i_0i_3\), \(o_4i_4\) are genuine Petersen edges (inner-pentagram edge and spoke respectively).A

o_2\!-\!o_1,\quad o_2\!-\!o_3\!-\!i_3,\quad o_2\!-\!i_2\!-\!i_4

All three edges at \(o_2\) used once each; \(o_3i_3\) is a spoke, \(i_2i_4\) is a pentagram edge — both genuine, and the internal vertices \(o_3,i_2\) have not been used in Step 3.A

i_1\!-\!o_1,\quad i_1\!-\!i_3,\quad i_1\!-\!i_4

All three are direct Petersen edges at \(i_1\) (one spoke, two pentagram edges), needing no internal vertices at all.B

\text{Petersen graph} \supseteq K_{3,3}\text{-subdivision} \implies \text{Petersen graph is non-planar}

Reading. The 9 paths above are pairwise internally disjoint (the four internal vertices \(o_3,o_4,i_0,i_2\) each occur in exactly one path, and no edge is reused), so together with the branch vertices \(A\cup B\) they exhibit an honest subdivision of \(K_{3,3}\) inside the Petersen graph.

Scope. This single example also shows why the edge-count bound \(m\le 3n-6\) is not by itself informative here: Petersen has \(n=10,m=15\), and \(3n-6=24\), comfortably satisfied — Kuratowski's finer criterion, not Euler's coarse count, is what is doing the real work.

\text{Let } G \text{ be } K_5 \text{ with one edge } uv \text{ replaced by a path } u\!-\!w\!-\!v \text{ through one new vertex } w. \text{ Determine planarity.}

\(G\) has \(n=6\) vertices, \(m=11\) edges (9 original \(K_5\) edges minus the one removed, plus 2 new ones: \(10-1+2=11\)).A

3n-6=3(6)-6=12,\qquad m=11\le 12.

Euler's necessary bound (Step 3 of the Proof) is satisfied, so the edge-count test alone is inconclusive — it does not certify planarity, only fails to rule it out.A

G \text{ literally contains a subdivision of } K_5: \text{ branch vertices are the original 5 vertices of } K_5, \text{ with the } u\!-\!v \text{ edge replaced by the length-2 path } u\!-\!w\!-\!v \text{ and every other pair joined by a direct edge.}

This matches Step 1's definition of subdivision exactly, with exactly one subdivided edge.B

G \text{ contains a } K_5\text{-subdivision} \implies G \text{ is non-planar}

Reading. Even though \(G\) comfortably satisfies the edge-count necessary condition for planarity, Kuratowski's theorem (via Step 6 of the Proof) shows the subdivision alone forces non-planarity — no drawing, however cleverly routed, can avoid a crossing.

Scope. Illustrates precisely why Kuratowski's criterion is strictly stronger than Euler's edge bound: the bound is necessary for planarity but never sufficient, whereas the subdivision test is both necessary and sufficient.

Problems

Show directly from Euler's formula (Step 2–3 of the Proof) that any planar graph has a vertex of degree at most 5.
Solution
Suppose every vertex of a simple planar graph \(G\) had degree \(\ge 6\). Then \(\sum_v \deg(v)\ge 6n\), and since \(\sum_v\deg(v)=2m\), this gives \(m\ge 3n\). But Step 3 gives \(m\le 3n-6\) for \(n\ge 3\), so \(3n\le m\le 3n-6\), i.e. \(0\le -6\), a contradiction. (For \(n\le 2\) the claim is trivial.) Hence some vertex has degree \(\le 5\).
The complete bipartite graph \(K_{2,4}\) — is it planar? Decide using Kuratowski's theorem (i.e. by looking for a forbidden subdivision, not just Euler's bound).
Solution
\(K_{2,4}\) has \(n=6,m=8\). Any \(K_5\)-subdivision needs 5 branch vertices of degree \(\ge4\); in \(K_{2,4}\) the two "size-2" side vertices have degree 4 but the four "size-4" side vertices only have degree 2, so at most 2 vertices are eligible as branch vertices of a \(K_5\)-subdivision — not enough. For \(K_{3,3}\): a subdivision needs 6 branch vertices of degree \(\ge 3\) each, but again only the 2 side vertices of \(K_{2,4}\) have degree \(\ge3\) (the other four have degree 2, and a subdivision cannot use degree-2 vertices as branch vertices unless \(H\) itself has a degree-2 vertex, which \(K_{3,3}\) does not). So \(K_{2,4}\) contains neither subdivision, and by Kuratowski's theorem is planar. (Directly: draw the two hubs \(a,b\) and route the four spoke-pairs \(a\!-\!x_i\!-\!b\) as nested arcs — an explicit planar drawing confirms this.)
Let \(G\) be the graph obtained from \(K_{3,3}\) by deleting a single edge. Is \(G\) planar? Justify via Kuratowski's theorem.
Solution
Yes. \(G=K_{3,3}-e\) has \(n=6,m=8\). If \(G\) contained a \(K_{3,3}\)-subdivision it would need at least 9 edges among its subdivision paths (since \(K_{3,3}\) has 9 edges and each contributes at least one edge to any subdivision), but \(G\) only has 8 edges total — impossible. A \(K_5\)-subdivision needs 5 branch vertices of degree \(\ge4\); in \(G\), only the two vertices incident to the removed edge \(e\) now have degree 2, and the rest have degree 3 — no vertex has degree \(\ge 4\), so no \(K_5\)-subdivision either. By Kuratowski's theorem \(G\) is planar. (One can also just draw it: \(K_{3,3}-e\) is a 6-cycle plus one chord, easily drawn without crossings.)
Prove that every graph with fewer than 9 edges is automatically planar, using Kuratowski's theorem together with a counting argument (do not just cite Euler's bound on the whole graph).
Solution
Suppose \(G\) has \(m\lt 9\) edges but is non-planar. By Kuratowski's theorem \(G\) contains a subdivision of \(K_5\) (which needs \(\ge 10\) edges, since each of \(K_5\)'s 10 edges becomes a path of length \(\ge1\)) or of \(K_{3,3}\) (which needs \(\ge9\) edges, similarly). Either way \(G\) has a subgraph with \(\ge9\) edges, forcing \(m\ge9\) — contradicting \(m\lt9\). Hence no such non-planar \(G\) exists, i.e. every graph with fewer than 9 edges is planar. (This is sharper than applying Euler's bound \(m\le 3n-6\) to \(G\) itself, which needs a lower bound on \(n\) to say anything.)
Let \(G\) be 3-connected, planar, and simple with \(n\ge5\) vertices, and let \(G^+\) be \(G\) with one extra edge added between two non-adjacent vertices \(x,y\). Explain, using the proof of Kuratowski's theorem (Steps 10–13), why \(G^+\) might or might not be planar, and what the theorem guarantees if it is not.
Solution
Fix a planar embedding of \(G\) (it exists since \(G\) is planar). If \(x\) and \(y\) lie on a common face boundary of some embedding of \(G\), then exactly as in Step 12 of the Proof, the new edge \(xy\) can be routed through that face without crossings, so \(G^+\) is planar. If in every planar embedding of \(G\) no face has both \(x\) and \(y\) on its boundary, then the argument of Step 13 applies verbatim to \(G\) in place of \(G'\): the failure to find a common face forces \(G+xy=G^+\) to contain a subdivision of \(K_5\) or \(K_{3,3}\), so by Kuratowski's theorem \(G^+\) is non-planar. So which case occurs is exactly decided by whether \(x,y\) co-bound a face — this is precisely the case distinction the Kuratowski proof turns on.