Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Face charges for rational dart transfers

Definition
FourColor_Discharging

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

four-color-theoremgraph-theory

Notation: D={0,…,n−1}D=\{0,\ldots,n-1\}D={0,…,n−1} is the dart set, n=∣D∣n = |D|n=∣D∣ its size, and p=νHp = \nu_Hp=νH​ is the node permutation. Write e,fe,fe,f for the edge and face permutations, with p(f(e(d)))=dp(f(e(d)))=dp(f(e(d)))=d. Edge, node and face counts E,N,FE,N,FE,N,F are numbers of permutation orbits, including singleton orbits. The component count CCC uses the equivalence generated by all three permutations. Planarity means the exact Euler equality E+N+F=n+2CE+N+F=n+2CE+N+F=n+2C, and connectedness means C=1C=1C=1.

A plain hypermap has a fixed-point-free involution eee. Cubic means every node orbit has size three; precubic means every node orbit has size at most three. Bridgeless means ddd and e(d)e(d)e(d) never lie in the same face orbit. A kkk-coloring is a map D→{0,…,k−1}D\to\{0,\ldots,k-1\}D→{0,…,k−1} 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 Fin⁡(m)\operatorname{Fin}(m)Fin(m); cubicity, connectedness and lower face-degree bounds are not assumed.

For any w:D→Qw:D\to\mathbb Qw:D→Q, define

qw(d)=60−10a(d)+∑y∼fd(w(e(y))−w(y)),Qw=∑d∈Dqw(d)/a(d).q_w(d)=60-10a(d)+\sum_{y\sim_f d}(w(e(y))-w(y)),\qquad Q_w=\sum_{d\in D}q_w(d)/a(d).qw​(d)=60−10a(d)+y∼f​d∑​(w(e(y))−w(y)),Qw​=d∈D∑​qw​(d)/a(d).

Here a(d)a(d)a(d) is the face-orbit size and is positive for every dart. The definitions alone do not assert a conserved total, a positive face, or validity of any rules. Formalization note: source-derived rational generalization of the concrete integer discharging formula. The separate conservation milestone establishes its total under planar/plain/cubic hypotheses.

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. 9, paragraph on PDF p. 9 defining discharging and its unnumbered charge formula; Section 5.5, PDF pp. 44–48. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/geometry.v#L617; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/discharge.v#L167; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/discharge.v#L201.

Definition code
import Definitions.Def_FourColor_Hypermap
import Mathlib.Data.Rat.Cast.Order
import Mathlib.Algebra.BigOperators.Field

/-!
Generic face charges, separating conservation from verification of particular rules.
Gonthier (2005), Section 3, PDF p. 9, unnumbered discharging formula;
pinned Rocq `discharge.v`, lines 167–172 and 201–216. Rational transfers generalize
the integer rule counts; no specific discharging rule or checker is assumed here.
-/

namespace FourColor.Hypermap

open scoped BigOperators

/-- The charge of the face containing `x`, with directed transfers along edge darts. -/
noncomputable def faceCharge {n : ℕ} (H : FourColor.Hypermap n)
    (transfer : Fin n → ℚ) (x : Fin n) : ℚ :=
  60 - 10 * (H.faceArity x : ℚ) +
    ∑ y ∈ H.faceDarts x, (transfer (H.edge y) - transfer y)

/-- Summing each face charge once, expressed without choosing orbit representatives. -/
noncomputable def totalFaceCharge {n : ℕ} (H : FourColor.Hypermap n)
    (transfer : Fin n → ℚ) : ℚ :=
  ∑ x : Fin n, H.faceCharge transfer x / (H.faceArity x : ℚ)

end FourColor.Hypermap
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. 9, paragraph on PDF p. 9 defining discharging and its unnumbered charge formula; Section 5.5, PDF pp. 44–48. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/geometry.v#L617; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/discharge.v#L167; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/discharge.v#L201.
Read-back

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

faceCharge. Let n∈Nn\in\mathbb Nn∈N, Dn={0,…,n−1}D_n=\{0,\ldots,n-1\}Dn​={0,…,n−1} (empty if n=0n=0n=0), and let H=(e,ν,ϕ)H=(e,\nu,\phi)H=(e,ν,ϕ) be three permutations of DnD_nDn​ with ν(ϕ(e(x)))=x\nu(\phi(e(x)))=xν(ϕ(e(x)))=x for every x∈Dnx\in D_nx∈Dn​. Write Fx={y∈Dn:∃j∈Z, ϕj(x)=y}F_x=\{y\in D_n:\exists j\in\mathbb Z,\ \phi^j(x)=y\}Fx​={y∈Dn​:∃j∈Z, ϕj(x)=y} and ax=∣Fx∣a_x=|F_x|ax​=∣Fx​∣, using inverse powers for negative jjj. For every function t:Dn→Qt:D_n\to\mathbb Qt:Dn​→Q and dart x∈Dnx\in D_nx∈Dn​, this rational number is 60−10ax+∑y∈Fx(t(e(y))−t(y))60-10a_x+\sum_{y\in F_x}(t(e(y))-t(y))60−10ax​+∑y∈Fx​​(t(e(y))−t(y)), with axa_xax​ converted to a rational number. The values of ttt are unrestricted in sign and size. No planarity equation, involution, connectedness, or node-cycle-size hypothesis is imposed. The set FxF_xFx​ contains xxx; if n=0n=0n=0 there is no argument xxx.

totalFaceCharge. Let n∈Nn\in\mathbb Nn∈N, Dn={0,…,n−1}D_n=\{0,\ldots,n-1\}Dn​={0,…,n−1} (empty if n=0n=0n=0), and let H=(e,ν,ϕ)H=(e,\nu,\phi)H=(e,ν,ϕ) be three permutations of DnD_nDn​ with ν(ϕ(e(x)))=x\nu(\phi(e(x)))=xν(ϕ(e(x)))=x for every x∈Dnx\in D_nx∈Dn​. Write Fx={y∈Dn:∃j∈Z, ϕj(x)=y}F_x=\{y\in D_n:\exists j\in\mathbb Z,\ \phi^j(x)=y\}Fx​={y∈Dn​:∃j∈Z, ϕj(x)=y} and ax=∣Fx∣a_x=|F_x|ax​=∣Fx​∣, using inverse powers for negative jjj. For every function t:Dn→Qt:D_n\to\mathbb Qt:Dn​→Q, this rational number is ∑x∈Dn(60−10ax+∑y∈Fx(t(e(y))−t(y)))/ax\sum_{x\in D_n}(60-10a_x+\sum_{y\in F_x}(t(e(y))-t(y)))/a_x∑x∈Dn​​(60−10ax​+∑y∈Fx​​(t(e(y))−t(y)))/ax​, with axa_xax​ converted to a rational number. The outer sum runs over darts, and each summand is divided by the size of its face cycle. The transfer values have no sign or size restriction, and no planarity equation, involution, connectedness, or node-cycle-size hypothesis is imposed. Each denominator in an existing term is positive since x∈Fxx\in F_xx∈Fx​. If n=0n=0n=0, the sum is empty and equals 000; no zero denominator occurs.

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