Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Four Color Theorem for finite planar graphs

Open
FourColor.four_color

by Minghui · Sep 26, 2026 · Mathlib c5ea003 (Lean v4.30.0)

four-color-theoremgraph-theory

Notation: VVV is the vertex type, GGG is a symmetric, irreflexive adjacency relation, and n=∣V∣n = |V|n=∣V∣ is the vertex count when VVV is finite. If ι:V→R2\iota:V\to\mathbb R^2ι:V→R2 places the vertices, p=ι(v)p = \iota(v)p=ι(v) denotes the point representing a vertex vvv. Edges are continuous injective arcs on [0,1][0,1][0,1] 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 VVV and every simple graph GGG on VVV,

IsPlanar⁡(G)⟹∃c:V→{0,1,2,3},∀v,w, G(v,w)⟹c(v)≠c(w).\operatorname{IsPlanar}(G)\Longrightarrow \exists c:V\to\{0,1,2,3\},\quad \forall v,w,\ G(v,w)\Longrightarrow c(v)\ne c(w).IsPlanar(G)⟹∃c:V→{0,1,2,3},∀v,w, G(v,w)⟹c(v)=c(w).

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).

Preamble
import Definitions.Def_FourColor_PlaneDrawing
Formal statement
namespace FourColor
universe u
theorem four_color :
  ∀ (V : Type u) [Finite V] (G : SimpleGraph V), IsPlanar G → G.Colorable 4 := by sorry
end FourColor
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).
Read-back

What the Lean code literally says, in plain math · gpt-6

four_color (proposed proposition). For every type VVV in an arbitrary universe uuu, assuming VVV is finite, and every simple graph GGG on VVV with symmetric, irreflexive adjacency, the existence of the following plane-drawing data implies the existence of a function c:V→{0,1,2,3}c:V\to\{0,1,2,3\}c:V→{0,1,2,3} such that G.Adj(v,w)G.\mathrm{Adj}(v,w)G.Adj(v,w) implies c(v)≠c(w)c(v)≠ c(w)c(v)=c(w) for every v,w∈Vv,w\in Vv,w∈V. The drawing data required in the hypothesis are an injective vertex map p:V→R2p:V\to\mathbb{R}^2p:V→R2 and, for every ordered adjacent pair v,wv,wv,w, a continuous injective path γv,w:[0,1]→R2\gamma_{v,w}:[0,1]\to\mathbb{R}^2γv,w​:[0,1]→R2 with γv,w(0)=p(v)\gamma_{v,w}(0)=p(v)γv,w​(0)=p(v) and γv,w(1)=p(w)\gamma_{v,w}(1)=p(w)γv,w​(1)=p(w), using the usual real and product topologies. They must satisfy γw,v(t)=γv,w(1−t)\gamma_{w,v}(t)=\gamma_{v,w}(1-t)γw,v​(t)=γv,w​(1−t) for every such pair and every t∈[0,1]t\in[0,1]t∈[0,1]; for every additional vertex xxx, γv,w(t)=p(x)\gamma_{v,w}(t)=p(x)γv,w​(t)=p(x) must imply x=vx=vx=v or x=wx=wx=w; and for every two adjacent pairs (v,w),(x,y)(v,w),(x,y)(v,w),(x,y) and every s,t∈[0,1]s,t\in[0,1]s,t∈[0,1], γv,w(s)=γx,y(t)\gamma_{v,w}(s)=\gamma_{x,y}(t)γv,w​(s)=γx,y​(t) must imply (v=x∧w=y)∨(v=y∧w=x)∨((s=0∨s=1)∧(t=0∨t=1))(v=x\land w=y)\lor(v=y\land w=x)\lor((s=0\lor s=1)\land(t=0\lor t=1))(v=x∧w=y)∨(v=y∧w=x)∨((s=0∨s=1)∧(t=0∨t=1)). Finiteness is assumed as a property of VVV, 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.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Minghui · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me