Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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 K5K_5 nor a K3,3K_{3,3} minor, equivalently neither subdivision

Statement

For every finite graph GG, the following are equivalent:

  1. GG is planar;
  2. GG has neither a K5K_5 nor a K3,3K_{3,3} minor;
  3. GG contains no subdivision of K5K_5 or K3,3K_{3,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 GG.

[L1]

A planar graph contains no subdivision of K5K_5 or K3,3K_{3,3} (A planar graph contains no subdivision of K5K_5 or K3,3K_{3,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 K5K_5 or K3,3K_{3,3} is three-connected).

[L3]

Every three-connected graph with no K5K_5 or K3,3K_{3,3} minor is planar (Every three-connected graph with no K5K_5 or K3,3K_{3,3} minor is planar).

[L4]

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

Proof

technique · direct
1.1

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

L1L4
2.1

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

step 1.1L2
3.1

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

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 · next 3 levels

Direct dependencies and their dependencies through the next three levels: 48 results over 15 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources