Four Color Theorem for finite planar graphs
OpenFourColor.four_colorNotation: is the vertex type, is a symmetric, irreflexive adjacency relation, and is the vertex count when is finite. If places the vertices, denotes the point representing a vertex . Edges are continuous injective arcs on with the prescribed endpoints, reversed consistently on reverse adjacency, avoiding all other vertices; distinct undirected edges intersect only at shared endpoints. The plane has its usual topology. There is no probability model.
For every finite vertex type and every simple graph on ,
All four colors need not be used. Empty graphs, isolated vertices and disconnected graphs are included; no connectedness, degree bound, chosen vertex enumeration, or decidability hypothesis is imposed. This is an existence theorem for proper vertex colorings. The adjacency representation does not distinguish parallel edges. A development using explicit multigraphs must justify the transfer.
Formalization note: the standard graph formulation of the source theorem.
Mathlib supplies SimpleGraph and Colorable; planarity is independently
defined by topological drawings. If proved through hypermaps, all graph
realization and color-transport steps must be formalized. The draft is an open
target; checking its statement does not prove it. Source: Robertson, Sanders, Seymour, Thomas, The Four-Colour Theorem, JCTB 70(1), 2–44 (1997), https://doi.org/10.1006/jctb.1997.1750; author manuscript https://people.math.gatech.edu/~thomas/PAP/fc.pdf, PDF p. 2, Section 1, paragraph 1 (unnumbered Four-Colour Theorem), and PDF p. 3, Section 2, drawing conventions. Gonthier, A Computer-Checked Proof of the Four Colour Theorem (2005), https://www.microsoft.com/en-us/research/wp-content/uploads/2012/10/4colproof.pdf, PDF p. 4, Section 2, paragraph beginning 'Although the statement' (graph embedding discussion; no numbered equation).
import Definitions.Def_FourColor_PlaneDrawing
namespace FourColor universe u theorem four_color : ∀ (V : Type u) [Finite V] (G : SimpleGraph V), IsPlanar G → G.Colorable 4 := by sorry end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
four_color (proposed proposition). For every type in an arbitrary universe , assuming is finite, and every simple graph on with symmetric, irreflexive adjacency, the existence of the following plane-drawing data implies the existence of a function such that implies for every . The drawing data required in the hypothesis are an injective vertex map and, for every ordered adjacent pair , a continuous injective path with and , using the usual real and product topologies. They must satisfy for every such pair and every ; for every additional vertex , must imply or ; and for every two adjacent pairs and every , must imply . Finiteness is assumed as a property of , with no enumeration, decidable equality, or decidable adjacency supplied. The coloring need not use all four colors and need not be unique, and the proposition specifies no coloring algorithm. There is no nonemptiness, connectedness, or minimum-size hypothesis: empty graphs, graphs on one vertex, disconnected graphs, and edgeless graphs are included. For the empty graph the coloring function is empty; for an edgeless graph the adjacency constraint on colors is vacuous. If the drawing hypothesis has no witness, the implication imposes no coloring conclusion for that graph. This is the quantified proposition being proposed, not an assertion that a proof has been supplied.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.