Alphabeta Math
LemmaStatement: 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.

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

Statement

Facts & Assumptions

Given: A three-connected finite graph G with neither forbidden minor.

[L1]

Every three-connected simple graph with more than four vertices has an edge whose simple contraction remains three-connected (Every three-connected simple graph with more than four vertices has an edge whose simple contraction remains three-connected).

[L2]

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 · induction
1.1

A three-connected graph of order four is K4, which has the usual plane drawing. Assume the result for smaller three-connected graphs that exclude the two minors.

baseL2
1.2

If ∣G∣>4, choose xy from [L1]. The contraction H=G/xy remains three-connected and excludes the forbidden minors because the minor relation is transitive. It has a plane drawing by the induction hypothesis.

ihL1
2.1

Let v be the contracted vertex and delete it from the plane drawing of H. Its incident faces merge into one face of H−v, and every former neighbour of v lies on that face boundary. Since H−v is two-connected, the boundary is a cycle C. Put X=NG(x)∖{y} and Y=NG(y)∖{x}, both viewed on C. Enumerate X cyclically and let the intervening X-arcs partition C.

step 1.2
3.1

All vertices of Y lie on one intervening X-arc. Otherwise two vertices of Y alternate on C with two vertices of X; the paths through x and y, together with the two arcs of C, form a subdivision of K3,3. The only remaining alternating degeneracy is three common neighbours of x,y, which together with x,y form a subdivision of K5. Both contradict [L2].

step 2.1L2
4.1

Delete from the drawing of H the edges at v corresponding only to Y∖X, and regard v as x. The arc of C containing Y bounds, together with the two adjacent x-edges, a face of this drawing by polygonal separation and face containment. Place y in that face, join it polygonally to all vertices of Y, and draw xy inside a small neighbourhood of x. The arcs have disjoint interiors and recover a plane drawing of G.

step 3.1construct
5.1

The base and contraction step prove the lemma for all finite orders.

step 1.1step 4.1discharge-induction∎

Depends on

Used by

Dependency tree · two levels

27 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