While this submission is a draft, it cannot be used by other submissions.

Proof of `The excluded-minor characterization of outerplanarity`

groundedproofs/Lax303502Proofs/OuterplanarExcludedMinors.lean · lax-303502

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

A finite graph admits a straight-line drawing on a circle exactly when it has neither a K4K₄ nor a K2,3K₂,₃ minor.

Proof strategy

Induction first splits disconnected graphs and graphs with a cut vertex; acyclic connected graphs use the tree construction. In the remaining case, a longest cycle must span: an outside component has two distinct attachments; consecutive attachments extend the cycle, and nonconsecutive attachments give a K2,3K₂,₃ minor. Put the spanning cycle in circular order. Two crossing chords would give a K4K₄ minor. Smaller pieces can be joined in separate arcs at a shared vertex, so induction handles arbitrary finite graphs.

For the forward direction, normalize an arbitrary circle drawing to rational circle parameters. Chords meet exactly when their endpoints alternate. Connected disjoint branch sets cannot alternate, so choosing one representative from each branch set preserves the circular drawing of every minor. Neither K4K₄ nor K2,3K₂,₃ admits such an order. All geometry, gluing, and minor witnesses are checked explicitly; no other open characterization is assumed.

Attribution

First checked Diestel, Graph Theory, sixth edition, Chapter 4, Exercise 23, which states this characterization without a worked solution. The direct longest-cycle argument is in Madeleine Leander, On the bunkbed conjecture (2009), Theorem 14, printed page 37. We supply the disconnected and cut-vertex reductions explicitly before using its argument for a graph with no cut vertex. The formal development also supplies the circle geometry and connected-branch-set argument for the forward implication.