Try
Draw a connected graph in the plane without crossings and count vertices, edges and faces, including the unbounded outer face. A triangle has three vertices, three edges and two faces, so n−m+f=2. Moving edges without creating crossings can change the drawing but preserves this relation. The theorem concerns a plane embedding, not a diagram with unmarked crossings treated ambiguously as vertices.
Predict
Predict which edge deletions preserve connectedness. An edge on a cycle can be removed without disconnecting the graph and merges two adjacent faces. A bridge cannot be removed in that way; it is incident to the same face on both sides. This distinction is the mechanism behind Euler’s formula and explains why facial boundary counts must count edge sides rather than only distinct edges.
Experiment
Compare two connected plane graphs.
| Graph | Vertices | Edges | Faces including outer |
|---|
| Tree on five vertices | 5 | 4 | 1 |
| Square with one diagonal | 4 | 5 | 3 |
Delete the diagonal from the second graph and observe one edge and one face disappear. Continue deleting cycle edges until reaching a tree, preserving n−m+f throughout.
Understand
For a finite connected plane graph, delete cycle edges until a spanning tree remains. Each deletion merges two faces and leaves vertices and connectivity unchanged. A tree has n−1 edges and one face, proving n−m+f=2. This argument uses the elementary plane-separation fact that a simple embedded cycle separates its inside from its outside. For a simple plane graph with n≥3, every facial boundary walk has length at least three and each edge side contributes once to the total 2m. Thus 3f≤2m and Euler yields m≤3n−6. In a simple bipartite plane graph, no odd cycle exists and facial walks have length at least four, giving m≤2n−4. Disconnected graphs satisfy the same edge bounds when n≥3, by connecting components with suitable added edges or treating sparse exceptions directly.
Apply
The complete graph K5 violates the first bound, and K_(3, 3) violates the bipartite bound. These are rigorous nonplanarity certificates. Passing either necessary inequality is not a complete planarity test. The full forbidden-subdivision characterization is a separate structural theorem, not proved by edge counting. For convex polyhedra, the edge graph embeds on the sphere and hence in the plane after choosing an outer face. If every face has p sides and q faces meet at each vertex, incidence counting gives pf=2m and qn=2m. Euler then forces 1/p+1/q>1/2. With p, q≥3, the only pairs are (3, 3),(3, 4),(4, 3),(3, 5),(5, 3). This is a combinatorial restriction, not by itself a construction or uniqueness proof for regular solids.
When an edge-count test misses the obstruction
Replace each of the nine edges of K₃,₃ by a path of length two, using a different new vertex on every path. The resulting graph has 15 vertices and 18 edges. It passes both 18≤3·15−6 and the bipartite bound 18≤2·15−4, yet it is nonplanar.
Proof of the certificate. Suppose a plane embedding existed. At a new degree-two vertex, join its two incident edge arcs into a single arc and forget that vertex. The arcs have disjoint interiors from all other edges; doing this for the nine distinct internal vertices creates a plane embedding of K₃,₃. That graph has 6 vertices and 9 edges, contradicting its necessary bipartite bound 9≤8. Therefore the subdivided graph is nonplanar. The same smoothing argument works for a displayed subdivision of K₅, whose 10 edges violate 3·5−6=9.
A usable certificate consists of distinct branch vertices and one path for each edge of the obstructing graph. Each path must follow actual graph edges; its internal vertices must be disjoint from every other path’s internal vertices and from all branch vertices. Extra edges elsewhere in the graph do not invalidate a certificate: first restrict to the listed subgraph. A rejected path list does not prove planarity; it only fails to establish this particular obstruction.
Changed written task. Subdivide each edge of K₃,₃ by k new vertices, k≥1. Count vertices and edges, then explain why a density test becomes weaker as k grows. Feedback: n=6+9k and m=9(k+1). Smoothing still gives the same obstruction, while the general planar upper bound grows as 12+27k. If each replacement path has even length the new graph is bipartite regardless of the original coloring; for this specific K₃,₃ family bipartiteness can also be preserved for odd path lengths by using its original bipartition. Do not infer a general subdivision parity rule from one example.
This first argument proves the obstruction direction. The structural-converse section below supplies the other direction that every nonplanar graph contains such a subdivision. The distinction follows the Illinois graph notes; a complete recognition algorithm needs further structural theory.
The complete characterization and its proof boundary
Kuratowski’s theorem. A finite graph is planar if and only if it contains no subdivision of K₅ or K₃,₃ as a subgraph. A subdivision replaces edges by internally vertex-disjoint paths. The subgraph need not be induced: unwanted additional edges can be deleted. Equivalently, Wagner’s formulation excludes K₅ and K₃,₃ as minors, where deletion and contraction are allowed. These equivalences do not say a fixed drawing must be crossing-free.
The obstruction implication was proved above. The converse is a structural theorem, not a consequence of Euler’s inequality. Compare the self-contained graph argument below with Diestel’s author-hosted Chapter 4, section 4.4, inspected 30 October 2026: Lemma 4.4.2 connects the two obstruction languages; Lemma 4.4.3 handles the 3-connected case; Lemma 4.4.5 supplies the reduction needed for Theorem 4.4.6. The section below supplies the graph lemmas and induction locally. Jordan disk separation is its explicit topological premise, already used for Euler; clicking a certificate checker still does not establish that a learner understands the proof.
Work with a certificate rather than the theorem’s name
Construct a graph with branches a,b,c on one side and u,v,w on the other. Replace every one of its nine edges by a two-edge path with a private intermediate vertex. Add an extra edge a–b. Write the nine paths as your certificate. The extra edge destroys the original obvious bipartition of the full graph, but the displayed subdivision subgraph still proves nonplanarity. It is invalid to apply the bipartite edge bound to the entire graph merely because the certificate’s branch graph is bipartite.
Now change the construction so all nine supposed paths share a single intermediate vertex z. The resulting graph can be just the six-leaf star centered at z, which is planar. Pairwise endpoint reachability is not enough: the path interiors must be disjoint. A validator must inspect every consecutive graph edge, the distinct branch labels, required branch-pair coverage, simplicity of each path and disjointness of every internal vertex. The added bounded certificate verifier checks those conditions; rejection means only that the proposed certificate failed.
A proof-reading assessment with explicit criteria
- Minor versus subdivision. Exhibit a K₄ minor in a graph obtained by subdividing each K₄ edge once, and explain why the graph contains no literal K₄ subgraph. Contract one edge of each replacement path to recover K₄. The original branch vertices have no direct edges between them, and each inserted vertex has degree 2, so no four vertices form a complete subgraph. This example distinguishes three relations without suggesting K₄ obstructs planarity.
- Why both forbidden types are needed. K₅ contains no K₃,₃ subdivision, because a subdivision needs at least six distinct branch vertices. K₃,₃ contains no K₅ subdivision, because each of its vertices has degree 3, whereas a K₅ branch vertex needs four incident path starts. Each is nonplanar by its own bound, so omitting either forbidden type changes the characterization.
- Repair a false converse. A classmate tests every five- and six-vertex induced subgraph and finds no K₅ or K₃,₃. Explain why this is not a planarity algorithm. The fifteen-vertex subdivided K₃,₃ example has no literal K₃,₃ or K₅ subgraph (its original branches are pairwise nonadjacent and inserted vertices have degree 2), yet is nonplanar. The theorem requires paths, not only direct adjacency.
- Read the structural proof. Submit a dependency diagram for the named primary-source lemmas, explain where 3-connectivity is needed, and reconstruct one reduction in your own words with a labeled graph. A reviewer must check the actual reduction, not merely the diagram’s presence. A proof that assumes the characterization to justify its own reduction is circular.
For computational work, retain the exact graph and path list. Compare a valid certificate with the shared-center counterexample, then change one edge and explain whether the existing certificate still works. These are public practice cases and independent endpoint verification, not an automatic grade for the structural proof or an implementation of a linear-time planarity recognizer.
Prove the structural converse
We now prove the finite graph implication that was previously a reading dependency. The topological premise is the same elementary Jordan separation used in Euler’s formula: a simple polygonal closed curve bounds a disk, and disjoint arcs drawn across that disk have the usual cyclic boundary order. Subdivision and small local rerouting allow polygonal drawings. We also use the elementary polygonal-disk deformation obtained by triangulating a disk and mapping corresponding triangles piecewise linearly. We do not claim here to prove the Jordan curve theorem itself.
We first prove that a finite simple graph with neither a K₅ nor a K₃,₃ minor is planar, by induction on its number of vertices. A minor is represented by disjoint connected branch sets, with an edge between the sets for each required adjacency. Deleting extra vertices/edges or contracting within connected sets cannot introduce a forbidden minor into a graph that has none: composition of these operations is still a sequence of deletions/contractions.
Lemma: some edge of a larger 3-connected graph can be contracted
For a 3-connected graph with more than four vertices, suppose every edge uv fails. A separator of size at most two after contraction must contain the contracted vertex, and lifts to a 3-vertex separator u,v,w; a smaller separator would contradict 3-connectivity. Choose such a separator and a component C of its deletion with |C| least possible. Every separator vertex has a neighbor in every component, or its other two vertices would separate that component. Pick z in C adjacent to w. By the supposition, deleting w,z,t for some t disconnects the graph. Since u,v are adjacent, all of those still present belong to one component. Choose another component D, avoiding u,v. Vertex z has a neighbor in D. That neighbor lies in C, since C’s only outside neighbors are u,v,w. Connectedness and avoidance of u,v,w imply D⊆C. But z is absent from D, so |D|<|C|, contradiction. Thus some contraction preserves3-connectivity.
Lemma: the hole left by a vertex has a simple cyclic boundary
In a plane 2-connected graph every face boundary is a cycle. To see the obstruction to this statement, trace the boundary of a face. A repeated vertex separates two nonempty portions of that boundary walk in its cyclic order. A small circle about that vertex exposes two corresponding sectors. Joining them through the face gives a separating closed curve meeting the graph only at that vertex. Any graph path between the two portions must meet it, making the repeated vertex a cut vertex. Bridges likewise force a repeated boundary passage and a cut vertex (apart from the single-edge exceptional graph). Neither is possible in a 2-connected graph of at least three vertices. Thus the boundary has no repetitions and is a simple cycle.
For a 3-connected plane graph H, deleting a vertex v leaves a 2-connected graph: deleting one additional vertex still leaves a connected graph by 3-connectivity. The face containing the former position of v consequently has a cycle boundary C. All neighbors of v lie on C, and its incident edges can be viewed as disjoint spokes inside this disk.
Expand one contracted edge, or exhibit a forbidden minor
A 3-connected graph on four vertices is K₄, which is planar. Now let G be 3-connected with at least five vertices and no forbidden minor. Choose an edge xy whose contraction H remains 3-connected. By induction H is planar. Let v be the contracted vertex and C the boundary cycle after deleting v. Write X=N_G(x) excluding y and Y=N_G(y) excluding x; both sets lie on C and each has at least two vertices. Keep the spokes from v to X and call their common endpoint x. We must add y, its edge to x, and its spokes to Y.
List X cyclically around C. Between consecutive members a,b of X, a gap means the closed a-to-b subpath containing no other X vertex. If Y is entirely in one gap, add y in the disk sector bounded by that subpath and the two spokes xa,xb. Draw its edges to all Y vertices and x as a noncrossing fan in that sector. This gives a drawing of G.
It remains to prove that failure of this placement contradicts the minor assumption, with actual path witnesses rather than a drawing slogan.
- Suppose p in Y lies in the interior of an X-gap from a to b, but q in Y lies outside that closed gap. The cyclic order is a,p,b,q. Use branch sets consisting of the six individual vertices, with bipartition
{x,p,q} and {y,a,b}. Five connecting paths are the edges xy,xa,xb,yp,yq. The remaining four are the four consecutive arcs of C between a,p,b,q. Their interiors are mutually disjoint and avoid x,y. This is a subdivision of K₃,₃. - Otherwise Y⊆X. If Y has at least three members a,b,c, use x,y,a,b,c as K₅ branches. The edges from both hubs to a,b,c, the edge xy, and the three successive a-b-c arcs of C give ten internally disjoint edge paths: a K₅ subdivision.
- If Y=
{p,q} and is not in one X-gap, p and q are not consecutive in either cyclic direction among X. Choose a in X on one open p-to-q arc and b in X on the other. The cycle order is p,a,q,b. The same nine-path construction with bipartition {x,p,q} and {y,a,b} gives a K₃,₃ subdivision.
The cases are exhaustive. If a Y vertex lies outside X, the first case applies unless all of Y is in its gap. If Y⊆X, its size is at least two and the remaining cases cover every failed gap placement. Thus a forbidden-minor-free 3-connected graph expands to a planar drawing.
Reduce graphs with small separators
The induction still needs graphs that are not3-connected. Graphs on at most three vertices are planar. Disconnected components can be drawn in disjoint disks. If a connected graph has a cut vertex a, its smaller induced pieces consisting of a and one component of G−a are minors and hence planar by induction. Put their drawings in disks meeting only at a; this proves planarity of their union.
Now assume G is 2-connected but has a separator {a,b}. Let C₁,…,C_k, k≥2, be the components of G−{a,b}. Each C_i has a neighbor of a and a neighbor of b; otherwise deleting the other one of a,b would disconnect it. Hence there is an a-to-b path whose interior lies in C_i. Define H_i on C_i together with a,b, including all its induced edges and the edge ab even when it is absent in G. H_i is a minor of G: use an a-to-b path through any different component, contract its interior to create ab, and delete the unused vertices. Each H_i is smaller than G and is planar by induction.
Choose in each drawing a face incident to ab as its outside face, delete that copy of ab, and regard the remaining drawing as lying in a closed disk touching the disk boundary only at a,b. This is achieved by a small inward deformation of the finite drawing away from its distinguished boundary edge; no other vertex is identified. Place these disks into disjoint narrow lenses joining a to b, with interiors disjoint and only their two endpoints shared. Their union draws all G edges except possibly ab. If ab belongs to G, draw one copy outside the lenses. Thus the gluing introduces no crossings. This completes the induction for the minor characterization.
Turn a forbidden minor into a forbidden subdivision
For K₃,₃, each branch set has three outgoing required edges. Retain a smallest tree in that set connecting their attachment points. Including the three outgoing half-edges, suppressing degree-two vertices leaves one degree-three junction. The three routes from that junction to the outgoing edges are internally disjoint, even when several edges attach at the same original vertex. Branch sets are disjoint, so joining these routes produces a K₃,₃ subdivision in G.
For a K₅ minor, do the same with four outgoing edges per branch set. After deleting unnecessary twigs and suppressing degree-two vertices, a tree with four terminal half-edges is either a four-armed star or two degree-three junctions joined by a path. This follows from the tree degree sum: the total excess Σ(degree−2) at internal vertices is two. If every branch tree is a star, its junctions and their disjoint routes give a K₅ subdivision.
If one branch tree has two junctions p,q, contract its connecting path to the edge pq and its four arms to attachments at p or q, two at each. Contract the other four branch sets to a,b,c,d so p meets a,b and q meets c,d. The four vertices a,b,c,d are mutually adjacent because they were K₅ branch sets. Delete unneeded edges. The bipartition {p,c,d} and {q,a,b} now has all nine cross-edges: pq,pa,pb,cq,ca,cb,dq,da,db. This is a K₃,₃ minor. The preceding three-port construction then yields a K₃,₃ subdivision in the original graph.
Therefore absence of both forbidden subdivisions implies absence of both forbidden minors, which the induction proves planar. The earlier smoothing/Euler proof establishes the converse implication. Together they prove the full characterization, not only its edge-density corollaries. The primary-source reading remains useful for comparison, but is no longer the only location of the structural argument.
Check the proof on an unfamiliar arrangement
Put X={a,b,c,d} in that order on a cycle and let Y contain one vertex p strictly between a,b and another q strictly between c,d. Name all nine K₃,₃ paths using the first case above, then explain why endpoints a,b,p,q are distinct. Next move q into the same open a-b gap as p. The obstruction construction no longer applies; show the disk sector in which y can be inserted. This is a change of cyclic order, not a change detectable from the sizes of X and Y alone. A reviewer should verify path interiors, the separator-minor construction and the two different four-port tree shapes before accepting a proof portfolio.
Continue
When analyzing a mesh, specify whether it is a planar graph, a sphere decomposition or a surface of another genus. The constant two changes for other closed surfaces, so a toroidal mesh should not be diagnosed as invalid merely for failing the planar formula. Also distinguish vertices created by actual connections from crossings that only occur in a poor drawing. A useful certificate includes the embedding or face boundary walks, the incidence count, and the precise assumptions behind the selected edge bound.
Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with use planar topology in coloring and dual graphs.
