Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite hypermaps, Euler planarity, coloring, and minimality

Definition
FourColor_Hypermap

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.

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.

Definition code
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
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.
Read-back

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

Hypermap. For each n∈Nn\in\mathbb Nn∈N, this structure consists of permutations e,ν,ϕe,\nu,\phie,ν,ϕ of Dn={0,…,n−1}D_n=\{0,\ldots,n-1\}Dn​={0,…,n−1} and the requirement ν(ϕ(e(x)))=x\nu(\phi(e(x)))=xν(ϕ(e(x)))=x for every x∈Dnx\in D_nx∈Dn​. It has no nonemptiness, involution, fixed-point exclusion, or cycle-size requirement. For n=0n=0n=0, the permutations are on the empty set and the requirement is vacuous.

SameFace. 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​. For x,y∈Dnx,y\in D_nx,y∈Dn​, this relation means ∃j∈Z, ϕj(x)=y\exists j\in\mathbb Z,\ \phi^j(x)=y∃j∈Z, ϕj(x)=y, using inverse powers for negative jjj and the identity for j=0j=0j=0. It includes x=yx=yx=y; for n=0n=0n=0 there are no arguments.

Link. 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​. For x,y∈Dnx,y\in D_nx,y∈Dn​, this relation means e(x)=y ∨ ν(x)=y ∨ ϕ(x)=ye(x)=y\ \vee\ \nu(x)=y\ \vee\ \phi(x)=ye(x)=y ∨ ν(x)=y ∨ ϕ(x)=y. It is the indicated directed relation without an added symmetry or transitivity condition. For n=0n=0n=0 there are no arguments.

SameComponent. 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​. For x,y∈Dnx,y\in D_nx,y∈Dn​, this means membership in the same class of the smallest equivalence relation containing (z,e(z))(z,e(z))(z,e(z)), (z,ν(z))(z,\nu(z))(z,ν(z)), and (z,ϕ(z))(z,\phi(z))(z,ϕ(z)) for all zzz. Thus a finite chain may follow those steps in either direction, and a chain of length zero is allowed. For n=0n=0n=0 there are no arguments.

edgeCount. 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​. This natural number counts the classes of DnD_nDn​ for x∼y  ⟺  ∃j∈Z, ej(x)=yx\sim y\iff\exists j\in\mathbb Z,\ e^j(x)=yx∼y⟺∃j∈Z, ej(x)=y, using inverse powers for negative jjj. Fixed points count as one-element classes. The count is 000 if n=0n=0n=0.

nodeCount. 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​. This natural number counts the classes of DnD_nDn​ for x∼y  ⟺  ∃j∈Z, νj(x)=yx\sim y\iff\exists j\in\mathbb Z,\ \nu^j(x)=yx∼y⟺∃j∈Z, νj(x)=y, using inverse powers for negative jjj. Fixed points count as one-element classes. The count is 000 if n=0n=0n=0.

faceCount. 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​. This natural number counts the classes of DnD_nDn​ for x∼y  ⟺  ∃j∈Z, ϕj(x)=yx\sim y\iff\exists j\in\mathbb Z,\ \phi^j(x)=yx∼y⟺∃j∈Z, ϕj(x)=y, using inverse powers for negative jjj. Fixed points count as one-element classes. The count is 000 if n=0n=0n=0.

componentCount. 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​. This natural number counts classes of the smallest equivalence relation containing (x,e(x))(x,e(x))(x,e(x)), (x,ν(x))(x,\nu(x))(x,ν(x)), and (x,ϕ(x))(x,\phi(x))(x,ϕ(x)) for all xxx. Reflexivity, symmetry, and transitivity are included. Only classes of darts are counted, so the count is 000 if n=0n=0n=0.

Planar. 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​. For a permutation σ\sigmaσ, a cycle is a class for x∼σy  ⟺  ∃j∈Z, σj(x)=yx\sim_\sigma y\iff\exists j\in\mathbb Z,\ \sigma^j(x)=yx∼σ​y⟺∃j∈Z, σj(x)=y, using inverse powers for negative jjj. Let E,N,FE,N,FE,N,F count the cycles of e,ν,ϕe,\nu,\phie,ν,ϕ, and let CCC count the classes of the equivalence relation generated by (x,e(x))(x,e(x))(x,e(x)), (x,ν(x))(x,\nu(x))(x,ν(x)), and (x,ϕ(x))(x,\phi(x))(x,ϕ(x)), allowing reflexivity, symmetry, and transitivity. This predicate means exactly E+N+F=n+2CE+N+F=n+2CE+N+F=n+2C as an equality of natural numbers. It includes no drawing as data. If n=0n=0n=0, all counts are zero and the predicate holds.

Connected. 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​. Let CCC be the number of classes of the equivalence relation generated by all pairs (x,e(x))(x,e(x))(x,e(x)), (x,ν(x))(x,\nu(x))(x,ν(x)), and (x,ϕ(x))(x,\phi(x))(x,ϕ(x)), with reflexivity, symmetry, and transitivity. This predicate means exactly C=1C=1C=1. If n=0n=0n=0, C=0C=0C=0 and the predicate is false.

Plain. 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​. This predicate means ∀x∈Dn, e(e(x))=x ∧ e(x)≠x\forall x\in D_n,\ e(e(x))=x\ \wedge\ e(x)\ne x∀x∈Dn​, e(e(x))=x ∧ e(x)=x: the edge permutation is an involution without fixed points. If n=0n=0n=0, the condition is vacuous.

nodeArity. 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​. For x∈Dnx\in D_nx∈Dn​, this natural number is ∣{y∈Dn:∃j∈Z, νj(x)=y}∣|\{y\in D_n:\exists j\in\mathbb Z,\ \nu^j(x)=y\}|∣{y∈Dn​:∃j∈Z, νj(x)=y}∣, with inverse powers for negative jjj. The set contains xxx, so the value is positive for every available argument. For n=0n=0n=0 there is no argument xxx.

Cubic. 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​. This predicate means ∣{y∈Dn:∃j∈Z, νj(x)=y}∣=3|\{y\in D_n:\exists j\in\mathbb Z,\ \nu^j(x)=y\}|=3∣{y∈Dn​:∃j∈Z, νj(x)=y}∣=3 for every x∈Dnx\in D_nx∈Dn​, using inverse powers for negative jjj. Every node cycle has exactly three elements. For n=0n=0n=0 the condition is vacuous.

Precubic. 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​. This predicate means ∣{y∈Dn:∃j∈Z, νj(x)=y}∣≤3|\{y\in D_n:\exists j\in\mathbb Z,\ \nu^j(x)=y\}|\le3∣{y∈Dn​:∃j∈Z, νj(x)=y}∣≤3 for every x∈Dnx\in D_nx∈Dn​, using inverse powers for negative jjj. Every existing node cycle therefore has size one, two, or three. For n=0n=0n=0 the condition is vacuous.

Cubic.precubic. 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​. If ∣{y∈Dn:∃j∈Z, νj(x)=y}∣=3|\{y\in D_n:\exists j\in\mathbb Z,\ \nu^j(x)=y\}|=3∣{y∈Dn​:∃j∈Z, νj(x)=y}∣=3 for every xxx, then that cardinality is at most 333 for every xxx, using inverse powers for negative jjj. Both universal conditions are vacuous if n=0n=0n=0.

faceDarts. 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​. For x∈Dnx\in D_nx∈Dn​, this finite set is 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}, using inverse powers for negative jjj. It contains the entire face cycle, including xxx. For n=0n=0n=0 there is no argument xxx.

faceArity. 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​. For x∈Dnx\in D_nx∈Dn​, this natural number is ∣{y∈Dn:∃j∈Z, ϕj(x)=y}∣|\{y\in D_n:\exists j\in\mathbb Z,\ \phi^j(x)=y\}|∣{y∈Dn​:∃j∈Z, ϕj(x)=y}∣, using inverse powers for negative jjj. It is positive because xxx belongs to the set. For n=0n=0n=0 there is no argument xxx.

Bridgeless. 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​. This predicate means ∀x∈Dn, ¬∃j∈Z, ϕj(x)=e(x)\forall x\in D_n,\ \neg\exists j\in\mathbb Z,\ \phi^j(x)=e(x)∀x∈Dn​, ¬∃j∈Z, ϕj(x)=e(x), using inverse powers for negative jjj. No dart shares a face cycle with its edge image. No involution condition is included. For n=0n=0n=0 the condition is vacuous.

Coloring. 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​. For any type AAA in any universe and any function c:Dn→Ac:D_n\to Ac:Dn​→A, this predicate is the conjunction of ∀x,y∈Dn, (∃j∈Z, ϕj(x)=y)⇒c(x)=c(y)\forall x,y\in D_n,\ (\exists j\in\mathbb Z,\ \phi^j(x)=y)\Rightarrow c(x)=c(y)∀x,y∈Dn​, (∃j∈Z, ϕj(x)=y)⇒c(x)=c(y) and ∀x∈Dn, c(e(x))≠c(x)\forall x\in D_n,\ c(e(x))\ne c(x)∀x∈Dn​, c(e(x))=c(x), with inverse powers for negative jjj. Surjectivity onto AAA is not required; AAA need not be finite or inhabited. If n=0n=0n=0, the empty function satisfies both conditions even for empty AAA. If n>0n>0n>0, there is no function to empty AAA.

Colorable. 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​. For every k∈Nk\in\mathbb Nk∈N, this predicate is the existence of c:Dn→{0,…,k−1}c:D_n\to\{0,\ldots,k-1\}c:Dn​→{0,…,k−1} such that c(x)=c(y)c(x)=c(y)c(x)=c(y) whenever ϕj(x)=y\phi^j(x)=yϕj(x)=y for some j∈Zj\in\mathbb Zj∈Z, and c(e(x))≠c(x)c(e(x))\ne c(x)c(e(x))=c(x) for every xxx, using inverse powers for negative jjj. All colors need not be used. For n=0n=0n=0 it holds for every kkk, including k=0k=0k=0. For n>0n>0n>0 it fails when k=0k=0k=0.

FourColorable. 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​. This abbreviation asserts the existence of c:Dn→{0,1,2,3}c:D_n\to\{0,1,2,3\}c:Dn​→{0,1,2,3} such that c(x)=c(y)c(x)=c(y)c(x)=c(y) whenever ϕj(x)=y\phi^j(x)=yϕj(x)=y for some j∈Zj\in\mathbb Zj∈Z, and c(e(x))≠c(x)c(e(x))\ne c(x)c(e(x))=c(x) for every xxx, using inverse powers for negative jjj. All four colors need not be used. For n=0n=0n=0 the empty function is a witness.

Admissible. 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​. For a permutation σ\sigmaσ, a cycle is a class for x∼σy  ⟺  ∃j∈Z, σj(x)=yx\sim_\sigma y\iff\exists j\in\mathbb Z,\ \sigma^j(x)=yx∼σ​y⟺∃j∈Z, σj(x)=y, using inverse powers for negative jjj. Let E,N,FE,N,FE,N,F count the cycles of e,ν,ϕe,\nu,\phie,ν,ϕ, and let CCC count the classes of the equivalence relation generated by (x,e(x))(x,e(x))(x,e(x)), (x,ν(x))(x,\nu(x))(x,ν(x)), and (x,ϕ(x))(x,\phi(x))(x,ϕ(x)), allowing reflexivity, symmetry, and transitivity. The four admissibility conditions are E+N+F=n+2CE+N+F=n+2CE+N+F=n+2C; no xxx and e(x)e(x)e(x) belong to the same ϕ\phiϕ-cycle; e(e(x))=xe(e(x))=xe(e(x))=x and e(x)≠xe(x)\ne xe(x)=x for all xxx; and every ν\nuν-cycle has at most three elements. This predicate is exactly their conjunction, with no connectedness condition. For n=0n=0n=0 the equality is 0=00=00=0 and the other conditions are vacuous, so it holds.

MinimalCounterexample. 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​. For a permutation σ\sigmaσ, a cycle is a class for x∼σy  ⟺  ∃j∈Z, σj(x)=yx\sim_\sigma y\iff\exists j\in\mathbb Z,\ \sigma^j(x)=yx∼σ​y⟺∃j∈Z, σj(x)=y, using inverse powers for negative jjj. Let E,N,FE,N,FE,N,F count the cycles of e,ν,ϕe,\nu,\phie,ν,ϕ, and let CCC count the classes of the equivalence relation generated by (x,e(x))(x,e(x))(x,e(x)), (x,ν(x))(x,\nu(x))(x,ν(x)), and (x,ϕ(x))(x,\phi(x))(x,ϕ(x)), allowing reflexivity, symmetry, and transitivity. The four admissibility conditions are E+N+F=n+2CE+N+F=n+2CE+N+F=n+2C; no xxx and e(x)e(x)e(x) belong to the same ϕ\phiϕ-cycle; e(e(x))=xe(e(x))=xe(e(x))=x and e(x)≠xe(x)\ne xe(x)=x for all xxx; and every ν\nuν-cycle has at most three elements. A four-color assignment is a function c:Dn→{0,1,2,3}c:D_n\to\{0,1,2,3\}c:Dn​→{0,1,2,3} constant on every ϕ\phiϕ-cycle and satisfying c(e(x))≠c(x)c(e(x))\ne c(x)c(e(x))=c(x) for all xxx; it need not use every color. This proposition requires that HHH satisfy all four admissibility conditions, admit no four-color assignment, and that for every natural number m<nm<nm<n and every triple K=(eK,νK,ϕK)K=(e_K,\nu_K,\phi_K)K=(eK​,νK​,ϕK​) of permutations of DmD_mDm​ with νK(ϕK(eK(x)))=x\nu_K(\phi_K(e_K(x)))=xνK​(ϕK​(eK​(x)))=x, if EK+NK+FK=m+2CKE_K+N_K+F_K=m+2C_KEK​+NK​+FK​=m+2CK​, no xxx shares a ϕK\phi_KϕK​-cycle with eK(x)e_K(x)eK​(x), eKe_KeK​ is an involution without fixed points, and all νK\nu_KνK​-cycles have size at most three, then a function cK:Dm→{0,1,2,3}c_K:D_m\to\{0,1,2,3\}cK​:Dm​→{0,1,2,3} constant on each ϕK\phi_KϕK​-cycle and satisfying cK(eK(x))≠cK(x)c_K(e_K(x))\ne c_K(x)cK​(eK​(x))=cK​(x) for every xxx exists. The counts for KKK use the cycle and generated-equivalence definitions on DmD_mDm​ stated above. Only strictly smaller dart counts are compared, with no comparison among triples on nnn darts. For n=0n=0n=0 the smaller-count requirement is vacuous, but the noncolorability requirement fails because the empty function is a coloring.

FourColorable.bridgeless. 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​. If there exists c:Dn→{0,1,2,3}c:D_n\to\{0,1,2,3\}c:Dn​→{0,1,2,3} such that c(x)=c(y)c(x)=c(y)c(x)=c(y) whenever ϕj(x)=y\phi^j(x)=yϕj(x)=y for some j∈Zj\in\mathbb Zj∈Z, and c(e(x))≠c(x)c(e(x))\ne c(x)c(e(x))=c(x) for every xxx, then ∀x∈Dn, ¬∃j∈Z, ϕj(x)=e(x)\forall x\in D_n,\ \neg\exists j\in\mathbb Z,\ \phi^j(x)=e(x)∀x∈Dn​, ¬∃j∈Z, ϕj(x)=e(x), with inverse powers for negative jjj. There is no hypothesis on cycle counts, an involution, connectedness, or node-cycle sizes. For n=0n=0n=0 the coloring exists and the conclusion is vacuous.

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