AFTD Auto-Formalizing Theoretical Domains

non_colorable_imp_partition_diam_gt

theoremverified

For every finite subset V of 3-dimensional Euclidean space and every real number t, if the distance threshold graph on V at threshold t (with edges between distinct points at distance greater than t) is not 4-colorable, then for every map c : V → Fin 4, there exists some color class whose diameter as a subset of Euclidean space is strictly greater than t.

Statement

theorem non_colorable_imp_partition_diam_gt
    (V : Finset (EuclideanSpace ℝ (Fin 3))) (t : ℝ)
    (hnot : ¬ (gale_distance_graph V t).Colorable 4)
    (c : V → Fin 4) :
    ∃ i : Fin 4, t < Metric.diam ((Subtype.val : V → EuclideanSpace ℝ (Fin 3)) '' (c ⁻¹' {i}))
Source
arXiv:2610.28828 -- A counterexample to Gale's conjecture in $\mathbb{R}^3$, Theorem 2
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • gale_distance_graphFor a finite subset V of the 3-dimensional Euclidean space EuclideanSpace ℝ (Fin 3) and a real number t, gale_distance_graph V t is…
Used by 1

Read back from the Lean

For any finite set V of points in the 3-dimensional Euclidean space EuclideanSpace ℝ (Fin 3) and any real number t, if the Gale distance graph on V with threshold t (the simple graph with vertex set V where distinct vertices u, v are adjacent if and only if their Euclidean distance is strictly greater than t) is not 4-colorable, then for every 4-coloring (partition into 4 sets) c : V → Fin 4, there exists a color class i : Fin 4 such that the metric diameter of the points in V assigned color i (that is, the diameter of Subtype.val '' (c ⁻¹' {i})) is strictly greater than t.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

We argue by contradiction: suppose there is a 4-coloring c of the vertex set V such that every color class has diameter at most t in 3-dimensional Euclidean space. If two vertices were adjacent in the distance threshold graph, their distance would strictly exceed t, meaning they could not belong to the same color class without violating the diameter bound. Consequently, c would be a proper 4-coloring of the threshold graph, contradicting the hypothesis that the graph is not 4-colorable.

  1. Assume for contradiction that every color class has diameter at most t.

    We begin a proof by contradiction using `by_contra!`. Negating the target existential statement gives the hypothesis h: for every color i ∈ {0, 1, 2, 3}, the diameter of the Euclidean image of the color class c⁻¹({i}) is at most t. The remaining goal is to derive a contradiction (False).

    line 7

      by_contra! h
  2. The coloring c is a proper 4-coloring of the threshold graph: any two adjacent vertices receive different colors.

    To show that c(u) ≠ c(v) for any adjacent vertices u and v, suppose for contradiction that c(u) = c(v). By definition of the distance threshold graph, adjacent vertices satisfy dist(u, v) > t. Let S be the Euclidean image of the color class c⁻¹({c(u)}). Both u and v belong to S. Since V is finite, the fiber is finite, so S is a finite set in ℝ³ (Set.toFinite) and therefore bounded. By Metric.dist_le_diam_of_mem, the distance between any two points in a bounded set is bounded by its diameter, so dist(u, v) ≤ diam(S). On the other hand, the contradiction hypothesis h implies diam(S) ≤ t. Combining these inequalities gives t < dist(u, v) ≤ diam(S) ≤ t, which is an immediate contradiction by linear arithmetic (linarith). Thus, adjacent vertices must receive different colors.

    lines 8–19

    uses Set.toFinite, Metric.dist_le_diam_of_mem

      have hc : ∀ {u v : V}, (gale_distance_graph V t).Adj u v → c u ≠ c v := by
        intro u v hadj hcuv
        have hadj' : t < dist (u : EuclideanSpace ℝ (Fin 3)) (v : EuclideanSpace ℝ (Fin 3)) := hadj.2
        set S := (Subtype.val : V → EuclideanSpace ℝ (Fin 3)) '' (c ⁻¹' {c u})
        have huS : (u : EuclideanSpace ℝ (Fin 3)) ∈ S := ⟨u, rfl, rfl⟩
        have hvS : (v : EuclideanSpace ℝ (Fin 3)) ∈ S := ⟨v, hcuv.symm, rfl⟩
        have hbound : Bornology.IsBounded S :=
          (Set.toFinite (c ⁻¹' {c u})).image (Subtype.val : V → EuclideanSpace ℝ (Fin 3)) |>.isBounded
        have hle1 : dist (u : EuclideanSpace ℝ (Fin 3)) (v : EuclideanSpace ℝ (Fin 3)) ≤ Metric.diam S :=
          Metric.dist_le_diam_of_mem hbound huS hvS
        have hle2 : Metric.diam S ≤ t := h (c u)
        linarith
  3. The threshold graph is 4-colorable, contradicting the assumption that it is not.

    Using SimpleGraph.Coloring.mk, the coloring function c together with the proof hc that it is proper defines a valid 4-coloring of the distance threshold graph. This witnesses that the graph is 4-colorable, which directly contradicts the hypothesis hnot that no such 4-coloring exists.

    line 20

    uses SimpleGraph.Coloring.mk

      exact hnot ⟨SimpleGraph.Coloring.mk c hc⟩
Set.toFinite
A subset of a type whose underlying subtype is finite is a finite set (Set.Finite).
Metric.dist_le_diam_of_mem
In a pseudometric space, the distance between any two points belonging to a bounded set is at most the diameter of that set.
SimpleGraph.Coloring.mk
Constructs a proper graph coloring from a coloring function and a proof that adjacent vertices receive distinct colors.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- If the distance threshold graph at threshold t on a finite set has no proper 4-coloring, then in every 4-coloring some color class has diameter strictly greater than t. -/theorem non_colorable_imp_partition_diam_gt    (V : Finset (EuclideanSpace ℝ (Fin 3))) (t : ℝ)    (hnot : ¬ (gale_distance_graph V t).Colorable 4)    (c : V → Fin 4) :    ∃ i : Fin 4, t < Metric.diam ((Subtype.val : V → EuclideanSpace ℝ (Fin 3)) '' (c ⁻¹' {i})) := by  by_contra! h  have hc : ∀ {u v : V}, (gale_distance_graph V t).Adj u v → c u ≠ c v := by    intro u v hadj hcuv    have hadj' : t < dist (u : EuclideanSpace ℝ (Fin 3)) (v : EuclideanSpace ℝ (Fin 3)) := hadj.2    set S := (Subtype.val : V → EuclideanSpace ℝ (Fin 3)) '' (c ⁻¹' {c u})    have huS : (u : EuclideanSpace ℝ (Fin 3)) ∈ S := ⟨u, rfl, rfl⟩    have hvS : (v : EuclideanSpace ℝ (Fin 3)) ∈ S := ⟨v, hcuv.symm, rfl⟩    have hbound : Bornology.IsBounded S :=      (Set.toFinite (c ⁻¹' {c u})).image (Subtype.val : V → EuclideanSpace ℝ (Fin 3)) |>.isBounded    have hle1 : dist (u : EuclideanSpace ℝ (Fin 3)) (v : EuclideanSpace ℝ (Fin 3)) ≤ Metric.diam S :=      Metric.dist_le_diam_of_mem hbound huS hvS    have hle2 : Metric.diam S ≤ t := h (c u)    linarith  exact hnot ⟨SimpleGraph.Coloring.mk c hc⟩
See it in the graphDiscuss this resultChallenge it