Finite hypermaps, Euler planarity, coloring, and minimality
DefinitionFourColor_HypermapNotation: is the dart set, its size, and is the node permutation. Write for the edge and face permutations, with . Edge, node and face counts are numbers of permutation orbits, including singleton orbits. The component count uses the equivalence generated by all three permutations. Planarity means the exact Euler equality , and connectedness means .
A plain hypermap has a fixed-point-free involution . Cubic means every node orbit has size three; precubic means every node orbit has size at most three. Bridgeless means and never lie in the same face orbit. A -coloring is a map constant on face orbits and different across each edge step. No requirement uses all available colors. The empty dart set has zero components, is planar, and is colorable, but is not connected.
An admissible hypermap is planar, bridgeless, plain and precubic. A minimal counterexample is a non-four-colorable admissible hypermap such that every admissible hypermap with fewer darts is four-colorable. Minimality includes all finite carriers through their enumeration by ; cubicity, connectedness and lower face-degree bounds are not assumed.
Formalization note: source-derived Lean-native definitions. Exact Euler equality replaces the source's genus expression; no topological equivalence or coloring theorem is assumed.
Source: Georges 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; Section 5.1, PDF p. 19, paragraph on PDF p. 19 giving the triangular identity; PDF p. 20, Euler formula; Section 3, PDF p. 7, minimal-counterexample paragraph. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hypermap.v#L112; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hypermap.v#L210; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/coloring.v#L224.
import Mathlib.GroupTheory.Perm.Cycle.Basic
import Mathlib.Logic.Relation
import Mathlib.SetTheory.Cardinal.Finite
/-!
# Finite hypermaps for the Four Color Theorem
This Lean-native interface follows Gonthier, *A computer-checked proof of the Four Colour
Theorem* (2005), Section 5.1, PDF pp. 17–20: the triangular identity is on p. 19 and the
unnumbered Euler formula is on p. 20. The finite carrier is `Fin dartCount`, so later
minimality statements can quantify over all finite hypermaps in a single universe.
The executable reference is rocq-community/fourcolor at commit
`c1d6b1cd5288bea4b067aac13cdde3c18dffe018`, under `theories/proof/`:
`hypermap.v` (`hypermap`, `glink`, `Euler_lhs`, `Euler_rhs`), `geometry.v`
(`plainP`, `cubicP`, `bridgeless`), and `coloring.v` (`coloring`, `four_colorable`).
The Rocq convention `cancel3 edge node face` means `node (face (edge x)) = x`.
Planarity below is the exact Euler equality, without truncated subtraction or division.
Correspondence with a topological graph drawing is a separate theorem obligation.
These definitions do not assert the Four Color Theorem or checker correctness.
-/
namespace FourColor
/-- A finite dart set with three permutations satisfying the hypermap triangular identity. -/
structure Hypermap (dartCount : ℕ) where
edge : Equiv.Perm (Fin dartCount)
node : Equiv.Perm (Fin dartCount)
face : Equiv.Perm (Fin dartCount)
edge_node_face : ∀ x, node (face (edge x)) = x
namespace Hypermap
variable {dartCount : ℕ}
/-- Darts on the same face, including the starting dart even for a singleton face. -/
def SameFace (H : Hypermap dartCount) : Fin dartCount → Fin dartCount → Prop :=
H.face.SameCycle
/-- One forward edge, node, or face step. Its generated equivalence gives components. -/
def Link (H : Hypermap dartCount) (x y : Fin dartCount) : Prop :=
H.edge x = y ∨ H.node x = y ∨ H.face x = y
/-- The equivalence relation generated by all three hypermap permutations. -/
def SameComponent (H : Hypermap dartCount) : Fin dartCount → Fin dartCount → Prop :=
Relation.EqvGen H.Link
/-- Number of edge orbits, counting singleton orbits as well. -/
noncomputable def edgeCount (H : Hypermap dartCount) : ℕ :=
Nat.card (Quotient (Equiv.Perm.SameCycle.setoid H.edge))
/-- Number of node orbits, counting singleton orbits as well. -/
noncomputable def nodeCount (H : Hypermap dartCount) : ℕ :=
Nat.card (Quotient (Equiv.Perm.SameCycle.setoid H.node))
/-- Number of face orbits, counting singleton orbits as well. -/
noncomputable def faceCount (H : Hypermap dartCount) : ℕ :=
Nat.card (Quotient (Equiv.Perm.SameCycle.setoid H.face))
/-- Number of connected components of the dart set. -/
noncomputable def componentCount (H : Hypermap dartCount) : ℕ :=
Nat.card (Quotient (Relation.EqvGen.setoid H.Link))
/-- Gonthier's generalized Euler equality, valid also for empty or disconnected hypermaps. -/
def Planar (H : Hypermap dartCount) : Prop :=
H.edgeCount + H.nodeCount + H.faceCount = dartCount + 2 * H.componentCount
/-- Connectedness includes nonemptiness: the empty hypermap has zero components. -/
def Connected (H : Hypermap dartCount) : Prop :=
H.componentCount = 1
/-- Every edge orbit has exactly two darts (`geometry.v`, `plainP`). -/
def Plain (H : Hypermap dartCount) : Prop :=
∀ x, H.edge (H.edge x) = x ∧ H.edge x ≠ x
/-- The cardinality of the node orbit containing a dart. -/
noncomputable def nodeArity (H : Hypermap dartCount) (x : Fin dartCount) : ℕ :=
Nat.card {y : Fin dartCount // H.node.SameCycle x y}
/-- Every node orbit has exactly three darts (`geometry.v`, `cubic`). -/
def Cubic (H : Hypermap dartCount) : Prop :=
∀ x, H.nodeArity x = 3
/-- Every node orbit has at most three darts (`geometry.v`, `precubic`). -/
def Precubic (H : Hypermap dartCount) : Prop :=
∀ x, H.nodeArity x ≤ 3
/-- Cubic maps satisfy the source's weaker precubic condition. -/
theorem Cubic.precubic {H : Hypermap dartCount} (h : H.Cubic) : H.Precubic := by
intro x
exact (h x).le
/-- The finite set of darts in the face containing `x`. -/
noncomputable def faceDarts (H : Hypermap dartCount) (x : Fin dartCount) :
Finset (Fin dartCount) := by
classical
exact Finset.univ.filter (H.SameFace x)
/-- The number of sides of the face containing a dart, counted with dart multiplicity. -/
noncomputable def faceArity (H : Hypermap dartCount) (x : Fin dartCount) : ℕ :=
(H.faceDarts x).card
/-- No edge step stays in the same face orbit (`geometry.v`, `bridgeless`). -/
def Bridgeless (H : Hypermap dartCount) : Prop :=
∀ x, ¬ H.SameFace x (H.edge x)
/-- A face coloring is constant on face orbits and changes color across every edge step. -/
def Coloring {α : Type*} (H : Hypermap dartCount) (color : Fin dartCount → α) : Prop :=
(∀ x y, H.SameFace x y → color x = color y) ∧
(∀ x, color (H.edge x) ≠ color x)
/-- Existence of a proper face coloring with at most `colorCount` colors. -/
def Colorable (H : Hypermap dartCount) (colorCount : ℕ) : Prop :=
∃ color : Fin dartCount → Fin colorCount, H.Coloring color
/-- Existence of a proper face coloring with at most four colors; surjectivity is not required. -/
abbrev FourColorable (H : Hypermap dartCount) : Prop :=
H.Colorable 4
/-- The class minimized in Gonthier's `coloring.v`, `minimal_counter_example`. -/
def Admissible (H : Hypermap dartCount) : Prop :=
H.Planar ∧ H.Bridgeless ∧ H.Plain ∧ H.Precubic
/-- A noncolorable member of the source's minimal class with the least number of darts.
The quantification over every `smaller : ℕ` includes the empty hypermap. Cubicity and
connectedness are conclusions to establish later, not additional assumptions here.
Source: Gonthier (2005), Section 3, PDF p. 7, minimal-counterexample paragraph;
precise dart-count formulation in pinned Rocq `coloring.v`, lines 224–231.
-/
structure MinimalCounterexample (H : Hypermap dartCount) : Prop where
admissible : H.Admissible
not_fourColorable : ¬ H.FourColorable
minimal : ∀ (smaller : ℕ), smaller < dartCount → ∀ K : Hypermap smaller,
K.Admissible → K.FourColorable
/-- A bridge obstructs face coloring because both ends would have the same color. -/
theorem FourColorable.bridgeless {H : Hypermap dartCount} (h : H.FourColorable) :
H.Bridgeless := by
obtain ⟨color, hface, hedge⟩ := h
intro x hsame
exact hedge x (hface x (H.edge x) hsame).symm
end Hypermap
end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
Hypermap. For each , this structure consists of permutations of and the requirement for every . It has no nonemptiness, involution, fixed-point exclusion, or cycle-size requirement. For , the permutations are on the empty set and the requirement is vacuous.
SameFace. Let , (empty if ), and let be three permutations of with for every . For , this relation means , using inverse powers for negative and the identity for . It includes ; for there are no arguments.
Link. Let , (empty if ), and let be three permutations of with for every . For , this relation means . It is the indicated directed relation without an added symmetry or transitivity condition. For there are no arguments.
SameComponent. Let , (empty if ), and let be three permutations of with for every . For , this means membership in the same class of the smallest equivalence relation containing , , and for all . Thus a finite chain may follow those steps in either direction, and a chain of length zero is allowed. For there are no arguments.
edgeCount. Let , (empty if ), and let be three permutations of with for every . This natural number counts the classes of for , using inverse powers for negative . Fixed points count as one-element classes. The count is if .
nodeCount. Let , (empty if ), and let be three permutations of with for every . This natural number counts the classes of for , using inverse powers for negative . Fixed points count as one-element classes. The count is if .
faceCount. Let , (empty if ), and let be three permutations of with for every . This natural number counts the classes of for , using inverse powers for negative . Fixed points count as one-element classes. The count is if .
componentCount. Let , (empty if ), and let be three permutations of with for every . This natural number counts classes of the smallest equivalence relation containing , , and for all . Reflexivity, symmetry, and transitivity are included. Only classes of darts are counted, so the count is if .
Planar. Let , (empty if ), and let be three permutations of with for every . For a permutation , a cycle is a class for , using inverse powers for negative . Let count the cycles of , and let count the classes of the equivalence relation generated by , , and , allowing reflexivity, symmetry, and transitivity. This predicate means exactly as an equality of natural numbers. It includes no drawing as data. If , all counts are zero and the predicate holds.
Connected. Let , (empty if ), and let be three permutations of with for every . Let be the number of classes of the equivalence relation generated by all pairs , , and , with reflexivity, symmetry, and transitivity. This predicate means exactly . If , and the predicate is false.
Plain. Let , (empty if ), and let be three permutations of with for every . This predicate means : the edge permutation is an involution without fixed points. If , the condition is vacuous.
nodeArity. Let , (empty if ), and let be three permutations of with for every . For , this natural number is , with inverse powers for negative . The set contains , so the value is positive for every available argument. For there is no argument .
Cubic. Let , (empty if ), and let be three permutations of with for every . This predicate means for every , using inverse powers for negative . Every node cycle has exactly three elements. For the condition is vacuous.
Precubic. Let , (empty if ), and let be three permutations of with for every . This predicate means for every , using inverse powers for negative . Every existing node cycle therefore has size one, two, or three. For the condition is vacuous.
Cubic.precubic. Let , (empty if ), and let be three permutations of with for every . If for every , then that cardinality is at most for every , using inverse powers for negative . Both universal conditions are vacuous if .
faceDarts. Let , (empty if ), and let be three permutations of with for every . For , this finite set is , using inverse powers for negative . It contains the entire face cycle, including . For there is no argument .
faceArity. Let , (empty if ), and let be three permutations of with for every . For , this natural number is , using inverse powers for negative . It is positive because belongs to the set. For there is no argument .
Bridgeless. Let , (empty if ), and let be three permutations of with for every . This predicate means , using inverse powers for negative . No dart shares a face cycle with its edge image. No involution condition is included. For the condition is vacuous.
Coloring. Let , (empty if ), and let be three permutations of with for every . For any type in any universe and any function , this predicate is the conjunction of and , with inverse powers for negative . Surjectivity onto is not required; need not be finite or inhabited. If , the empty function satisfies both conditions even for empty . If , there is no function to empty .
Colorable. Let , (empty if ), and let be three permutations of with for every . For every , this predicate is the existence of such that whenever for some , and for every , using inverse powers for negative . All colors need not be used. For it holds for every , including . For it fails when .
FourColorable. Let , (empty if ), and let be three permutations of with for every . This abbreviation asserts the existence of such that whenever for some , and for every , using inverse powers for negative . All four colors need not be used. For the empty function is a witness.
Admissible. Let , (empty if ), and let be three permutations of with for every . For a permutation , a cycle is a class for , using inverse powers for negative . Let count the cycles of , and let count the classes of the equivalence relation generated by , , and , allowing reflexivity, symmetry, and transitivity. The four admissibility conditions are ; no and belong to the same -cycle; and for all ; and every -cycle has at most three elements. This predicate is exactly their conjunction, with no connectedness condition. For the equality is and the other conditions are vacuous, so it holds.
MinimalCounterexample. Let , (empty if ), and let be three permutations of with for every . For a permutation , a cycle is a class for , using inverse powers for negative . Let count the cycles of , and let count the classes of the equivalence relation generated by , , and , allowing reflexivity, symmetry, and transitivity. The four admissibility conditions are ; no and belong to the same -cycle; and for all ; and every -cycle has at most three elements. A four-color assignment is a function constant on every -cycle and satisfying for all ; it need not use every color. This proposition requires that satisfy all four admissibility conditions, admit no four-color assignment, and that for every natural number and every triple of permutations of with , if , no shares a -cycle with , is an involution without fixed points, and all -cycles have size at most three, then a function constant on each -cycle and satisfying for every exists. The counts for use the cycle and generated-equivalence definitions on stated above. Only strictly smaller dart counts are compared, with no comparison among triples on darts. For the smaller-count requirement is vacuous, but the noncolorability requirement fails because the empty function is a coloring.
FourColorable.bridgeless. Let , (empty if ), and let be three permutations of with for every . If there exists such that whenever for some , and for every , then , with inverse powers for negative . There is no hypothesis on cycle counts, an involution, connectedness, or node-cycle sizes. For the coloring exists and the conclusion is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.