Planar drawings of simple graphs in the real plane
DefinitionFourColor_PlaneDrawingNotation: 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.
A plane drawing is the data described above, and means such a drawing exists. The definition itself does not assume finiteness; the mission theorem does. It neither mentions a coloring nor assumes the result of any configuration checker.
Formalization note: a source-derived Lean encoding of the graph-embedding formulation, using Mathlib paths and simple graphs. It is not a literal port of Gonthier's topological-map or hypermap definitions. 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 Mathlib.Combinatorics.SimpleGraph.Coloring.VertexColoring
import Mathlib.Topology.Path
/-!
A topological drawing of a simple graph in the real plane.
The definition is independent of coloring and of any reducibility certificate.
-/
namespace FourColor
universe u
/-- Vertices are distinct points, and edges are simple arcs that meet only at shared endpoints. -/
structure PlaneDrawing {V : Type u} (G : SimpleGraph V) where
vertex : V → ℝ × ℝ
vertex_injective : Function.Injective vertex
arc : ∀ {v w : V}, G.Adj v w → Path (vertex v) (vertex w)
arc_injective : ∀ {v w : V} (h : G.Adj v w), Function.Injective (arc h)
arc_reverse : ∀ {v w : V} (h : G.Adj v w), arc (G.symm h) = (arc h).symm
arc_avoids_vertices : ∀ {v w : V} (h : G.Adj v w) (t : unitInterval) (x : V),
arc h t = vertex x → x = v ∨ x = w
arcs_meet_only_at_endpoints :
∀ {v w x y : V} (h : G.Adj v w) (k : G.Adj x y) (s t : unitInterval),
arc h s = arc k t →
(v = x ∧ w = y) ∨ (v = y ∧ w = x) ∨
((s = 0 ∨ s = 1) ∧ (t = 0 ∨ t = 1))
/-- Existence of a crossing-free drawing by simple continuous arcs in the real plane. -/
def IsPlanar {V : Type u} (G : SimpleGraph V) : Prop :=
Nonempty (PlaneDrawing G)
end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
PlaneDrawing. For a type in an arbitrary universe and a simple graph on , whose adjacency relation is symmetric and irreflexive, a plane drawing consists of an injective function and, for every ordered pair with , a continuous injective function satisfying and , where the plane has its usual product topology and is the closed real unit interval. The function assigned to the reversed adjacency must be exactly the reversed parametrization: for every . For every adjacent , every , and every vertex , the equality implies or . For all adjacent pairs and and all , the equality implies the precise disjunction . Thus the last condition permits unrestricted intersection parameters when the two ordered pairs represent the same edge, while all other intersections must occur at endpoint parameters on both paths; the endpoint equations and injectivity of then identify a shared vertex. No finiteness, nonemptiness, connectedness, topology on , decidable equality on , or decidability of adjacency is assumed. For an edgeless graph all path conditions are vacuous, but an injective map of its vertices into the plane is still required; the empty graph and a graph on one vertex are included.
IsPlanar. For a type in an arbitrary universe and a simple graph on with symmetric, irreflexive adjacency, is the proposition that there exists at least one drawing with the following data and properties: an injective vertex map , and for every ordered adjacent pair a continuous injective path from at parameter to at parameter , using the usual real and product topologies. For all such pairs and all , ; for every , implies or ; and for all adjacent pairs and all , equality of and implies . Existence is asserted without uniqueness or a selected drawing. There is no finiteness, nonemptiness, connectedness, or decidability hypothesis. Empty and singleton vertex types are allowed; for an edgeless graph this proposition asks only for an injective map from its vertex type into the plane.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.