Sections 5.2–5.5 — Eliminate minimal counterexamples
OpenFourColor.no_minimal_counterexampleThere is no minimal counterexample in the finite planar, bridgeless, plain, precubic comparison class:
There is no hypothesis granting a successful external program run, correctness of a checker, reducibility of a catalogue, or validity of discharge rules.
Formalization note: the combined source-backed reducibility/unavoidability
endpoint. The source's conditional unavoidability is used only after proving
the genuine reducibility theorem. This remains the substantial finite-case-analysis
frontier: formalize configuration/contraction/Kempe semantics, the stronger
Birkhoff ring and embedding facts, a concrete source catalogue (633 entries in
the reference), sound finite checkers, all required certificate checks, and
the discharging case coverage. Structure and conservation alone do not prove it.
Notation: 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.
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 3, PDF p. 8, paragraph on PDF p. 8 listing reducibility and unavoidability; Section 5.2, PDF pp. 26–32; Section 5.4, PDF pp. 38–44; Section 5.5, PDF pp. 44–48. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/reducibility.v#L16; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/unavoidability.v#L20; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/configurations.v#L17.
import Definitions.Def_FourColor_Hypermap
namespace FourColor universe u theorem no_minimal_counterexample : ∀ (n : ℕ) (H : Hypermap n), ¬ H.MinimalCounterexample := by sorry end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
NoMinimalCounterexample. For every , a triple on means three permutations satisfying for every . A -cycle is a class for , with inverse powers for negative . Let count its edge, node, and face cycles, and let count the classes of the equivalence relation generated by every edge, node, and face permutation step, including reflexivity, symmetry, and transitivity. Condition means , no shares a -cycle with , and for every , and every -cycle has at most three elements. A coloring means a function constant on every -cycle and satisfying for every , without requiring every color to be used. The proposition says that for every and every such triple on , it is not the case that all three of the following hold together: satisfies ; has no coloring; and for every natural number and every such triple on , if satisfies then has a coloring. There is no hypothesis restricting the universally quantified . If , the smaller-count condition is vacuous but the noncolorability condition is false because the empty coloring exists.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.