Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-11
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Kuratowski–Wagner theorem: a finite graph is planar exactly when it has neither a K5 nor a K3,3 minor, equivalently neither subdivision

Statement

For every finite graph G, the following are equivalent:

  1. G is planar;
  2. G has neither a K5 nor a K3,3 minor;
  3. G contains no subdivision of K5 or K3,3.

Minor and subdivision have the meanings of Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors.

Facts & Assumptions

Given: A finite graph G.

[L1]

A planar graph contains no subdivision of K5 or K3,3 (A planar graph contains no subdivision of K5 or K3,3).

[L2]

Every edge-maximal graph of order at least four with no such subdivision is three-connected (Every edge-maximal graph of order at least four with no subdivision of K5 or K3,3 is three-connected).

[L3]

Every three-connected graph with no K5 or K3,3 minor is planar (Every three-connected graph with no K5 or K3,3 minor is planar).

[L4]

A graph has a K5 or K3,3 minor exactly when it contains a subdivision of one of them (A graph has a K5 or K3,3 minor exactly when it has a subdivision of K5 or K3,3 as a subgraph).

Proof

technique · direct
1.1

If G is planar, [L1] excludes both subdivisions. By [L4] it also excludes both minors.

L1L4
2.1

Conversely, suppose G contains neither subdivision. On its fixed finite vertex set, add edges until reaching an edge-maximal graph H with the same exclusion. If ∣V(G)∣<4, then G is plainly planar; otherwise [L2] makes H three-connected.

step 1.1L2
3.1

By [L4], H has neither forbidden minor. Apply [L3] to obtain a plane drawing of H; deleting the added edges leaves a plane drawing of G.

step 2.1L3L4
4.1

Step 1.1 proves planarity implies both exclusions, step 3.1 proves subdivision exclusion implies planarity, and [L4] identifies the two exclusion conditions. Thus all three assertions are equivalent.

step 1.1step 3.1L4∎

Depends on

Used by

Dependency tree · two levels

20 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources