Five Colour Theorem (Diestel, Proposition 5.1.2)
OpenDiestelGraphTheory.five_colour_theoremLet be a finite simple graph. If is planar, i.e. isomorphic to the abstract graph of a plane graph whose edges are polygonal arcs, then is -colourable: there is a map
This is the strongest colouring bound for planar graphs with a short proof; the Four Colour Theorem improves to .
Formalization Note -colourability is Mathlib's SimpleGraph.Colorable 5. The vertex type is assumed finite, as are all graphs in Diestel.
import Mathlib import Definitions.Def_DiestelGraphTheory_PolygonalArc import Definitions.Def_DiestelGraphTheory_PlaneGraph
namespace DiestelGraphTheory
theorem five_colour_theorem {V : Type*} [Finite V] (G : SimpleGraph V) (hG : IsPlanar G) :
G.Colorable 5 := by sorry
end DiestelGraphTheoryRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a finite type (in any universe) and a simple graph with vertex set . Assume is planar: there exist a plane graph and a graph isomorphism between and the abstract graph of (a bijection preserving and reflecting adjacency).
Here a plane graph is a finite set and a finite set of subsets of (plane = with product topology) such that
- each is an arc between some : a finite union of closed non-degenerate straight segments that is the image of a topological embedding with , (so );
- writing for the set of points such that is an arc between and some point or between some point and , distinct edges have distinct ;
- the interior of each edge contains no vertex, and for , ;
and its abstract graph has vertex set , with distinct adjacent iff some is an arc between and (or between and ).
Then is -colourable: there is a map with whenever and are adjacent in .
The finiteness assumption on is redundant given planarity (the isomorphism puts in bijection with the finite set ). The empty graph () is included and trivially satisfies the conclusion.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.