Section 3 — Cubicity, connectedness, and minimum face arity
OpenFourColor.minimal_counterexample_structureEvery dart-minimal counterexample in the admissible class is cubic, connected, and has no face with fewer than five darts:
where is the cardinality of the face orbit containing .
Formalization note: a conjunction of three source results. Cubicity follows from the precubic comparison class, connectedness from component reduction, and the face-arity bound from the local/Birkhoff reductions. This statement does not claim the stronger small-ring Birkhoff theorem or configuration embedding theory; those remain part of the finite-case-analysis development.
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. 7, paragraph on PDF p. 7 discussing local reductions, and PDF p. 8, Birkhoff discussion; Section 5.4, PDF pp. 38–39. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/coloring.v#L233; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/patch.v#L619; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/birkhoff.v#L493.
import Definitions.Def_FourColor_Hypermap
namespace FourColor
universe u
theorem minimal_counterexample_structure :
∀ (n : ℕ) (H : Hypermap n), H.MinimalCounterexample →
H.Cubic ∧ H.Connected ∧ ∀ x : Fin n, 5 ≤ H.faceArity x := by sorry
end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
MinimalCounterexampleStructure. 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 , if satisfies , has no coloring, and every such triple on every with satisfying has a coloring, then every -cycle has exactly three elements, , and for every . The lower bound on face size is quantified over every dart. The quantifiers include , but then the noncolorability hypothesis is impossible because an empty coloring exists.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.