AFTD Auto-Formalizing Theoretical Domains

graph_11_mutual_visibility_chromatic_number_eq_three

theoremverifiedformalization

The simple graph G_11 has mutual-visibility chromatic number 3, chromatic number 3, and diameter 2.

Statement

theorem graph_11_mutual_visibility_chromatic_number_eq_three :
    graph_mutual_visibility_chromatic_number graph_11 = 3 ∧
    graph_11.chromaticNumber = 3 ∧
    graph_11.diam = 2
Formalizes
arXiv:2610.39430 Theorem 3.4
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 1

Read back from the Lean

For the 11-vertex simple graph graph_11 on the vertex set Fin 11—obtained from the symmetric, loopless closure of the directed edges (0,1), (1,2), (2,3), (3,0), (4,0), (4,1), (5,1), (5,2), (6,2), (6,3), (7,3), (7,0), (8,4), (8,6), (9,5), (9,7), and (10,v) for each v ∈ {4, 5, 6, 7, 8, 9}—the following three conditions hold simultaneously: 1. The mutual-visibility chromatic number of graph_11 is equal to 3 (where the mutual-visibility chromatic number is the infimum in ℕ∞ of all n : ℕ such that the vertices can be colored with n colors such that every color class S is a mutual-visibility set, meaning that for every pair of vertices u, v ∈ S, there exists a shortest walk in the graph between u and v containing no vertices of S other than u and v); 2. The graph chromatic number of graph_11 is equal to 3; and 3. The diameter of graph_11 is equal to 2.

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

The chromatic number (χ(G_11) = 3) and diameter (diam(G_11) = 2) are already known, so it remains to determine the mutual-visibility chromatic number μ(G_11). Because G_11 has diameter 2, a general theorem bounds its mutual-visibility chromatic number above by its chromatic number, giving μ(G_11) ≤ 3. For the lower bound, any mutual-visibility n-coloring with n < 3 would imply, by monotonicity of colorability, that G_11 is 2-colorable, contradicting a known impossibility theorem. Combining both bounds by antisymmetry shows that μ(G_11) = 3.

  1. The empty set of vertices is a mutual-visibility set in any graph G.

    The definition of a mutual-visibility set requires that every pair of vertices u, v in the set can see each other via a geodesic whose interior vertices are outside the set. This condition holds vacuously for the empty set: since no vertex u can belong to ∅, the hypothesis u ∈ ∅ is eliminated via False.elim.

    lines 4–5

    uses False.elim

      intro u hu
      exact False.elim hu
  2. A mutual-visibility n-coloring extends to an m-coloring for any m ≥ n by composing with the canonical embedding.

    Given a valid coloring c : V → Fin n whose color classes are mutual-visibility sets, the canonical order embedding Fin.castLEOrderEmb embeds Fin n into Fin m. We propose the composite function v ↦ emb(c(v)) as an m-coloring of G.

    lines 11–13

    uses Fin.castLEOrderEmb

      obtain ⟨c, hc⟩ := hc
      let emb : Fin n ↪ Fin m := (Fin.castLEOrderEmb hnm).toEmbedding
      use fun v => emb (c v)
  3. For each color in the image of the embedding, the corresponding color class is a mutual-visibility set.

    For any color i ∈ Fin m, we case-split on whether i is in the image of emb. If i = emb(j) for some j ∈ Fin n, injectivity of emb ensures that the fiber {v | emb(c(v)) = emb(j)} is identical to the original color class {v | c(v) = j}, which is a mutual-visibility set by the assumption on c.

    lines 14–21

      intro i
      by_cases hi : ∃ j : Fin n, emb j = i
      · rcases hi with ⟨j, rfl⟩
        have : {v | emb (c v) = emb j} = {v | c v = j} := by
          ext v
          simp [emb.injective.eq_iff]
        rw [this]
        exact hc j
  4. For each color outside the image of the embedding, the corresponding color class is empty and therefore a mutual-visibility set.

    If i ∈ Fin m is not in the image of emb, no vertex v is assigned color i, so the fiber {v | emb(c(v)) = i} is empty. By the helper lemma graph_11_mutual_visibility_chromatic_number_eq_three_empty_is_mutual_visibility_set, the empty set is a mutual-visibility set, completing the proof that the extended coloring is a valid mutual-visibility m-coloring.

    lines 22–28

    uses Set.mem_empty_iff_false, iff_false, graph_11_mutual_visibility_chromatic_number_eq_three_empty_is_mutual_visibility_set

      · have : {v | emb (c v) = i} = ∅ := by
          ext v
          simp only [Set.mem_empty_iff_false, iff_false]
          intro h_eq
          exact hi ⟨c v, h_eq⟩
        rw [this]
        exact graph_11_mutual_visibility_chromatic_number_eq_three_empty_is_mutual_visibility_set G
  5. The theorem reduces to proving that the mutual-visibility chromatic number of G_11 is 3.

    The theorem asserts a conjunction of three facts: graph_mutual_visibility_chromatic_number graph_11 = 3, chromaticNumber = 3, and diam = 2. The second and third parts are supplied directly by the existing results graph_11_chromatic_number and graph_11_diam, leaving only the mutual-visibility chromatic number to be established.

    line 35

    uses graph_11_chromatic_number, graph_11_diam

      refine ⟨?_, graph_11_chromatic_number, graph_11_diam⟩
  6. The mutual-visibility chromatic number of G_11 is at most 3.

    By graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two, any graph with diameter 2 has mutual-visibility chromatic number at most its chromatic number. Using the known diameter 2 (graph_11_diam) and chromatic number 3 (graph_11_chromatic_number), this gives graph_mutual_visibility_chromatic_number graph_11 ≤ 3.

    lines 36–39

    uses graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two, graph_11_diam, graph_11_chromatic_number

      have hle : graph_mutual_visibility_chromatic_number graph_11 ≤ 3 := by
        have h := graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two graph_11 graph_11_diam
        rw [graph_11_chromatic_number] at h
        exact h
  7. To show 3 ≤ graph_mutual_visibility_chromatic_number graph_11, it suffices to show 3 ≤ n for every n such that G_11 is mutual-visibility n-colorable.

    The mutual-visibility chromatic number is defined as the infimum of all n ∈ ℕ such that G_11 is mutual-visibility n-colorable. Applying the universal property of infima (le_iInf) twice reduces the lower bound 3 ≤ inf to showing 3 ≤ n for an arbitrary valid coloring with n colors.

    lines 40–46

    uses le_iInf

      have hge : (3 : ℕ∞) ≤ graph_mutual_visibility_chromatic_number graph_11 := by
        dsimp [graph_mutual_visibility_chromatic_number]
        apply le_iInf
        intro n
        apply le_iInf
        intro hn
        change graph_is_mutual_visibility_colorable graph_11 n at hn
  8. Every valid mutual-visibility coloring of G_11 requires at least 3 colors.

    We proceed by contradiction, assuming n < 3, which implies n ≤ 2 since n is a natural number. By the monotonicity lemma graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono, an n-coloring with n ≤ 2 would imply that G_11 is mutual-visibility 2-colorable. But this contradicts graph_11_not_is_mutual_visibility_colorable_two, completing the contradiction and establishing 3 ≤ n.

    lines 47–53

    uses graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono, graph_11_not_is_mutual_visibility_colorable_two

        by_contra! hlt
        have hle2 : n ≤ 2 := by
          norm_cast at hlt
          omega
        have h2 : graph_is_mutual_visibility_colorable graph_11 2 :=
          graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono graph_11 hle2 hn
        exact graph_11_not_is_mutual_visibility_colorable_two h2
  9. The mutual-visibility chromatic number of G_11 is 3.

    Combining the upper bound graph_mutual_visibility_chromatic_number graph_11 ≤ 3 with the lower bound 3 ≤ graph_mutual_visibility_chromatic_number graph_11 via antisymmetry of the ordering (le_antisymm) yields graph_mutual_visibility_chromatic_number graph_11 = 3.

    line 54

    uses le_antisymm

      exact le_antisymm hle hge
False.elim
From a proof of False, any proposition can be deduced (the principle of explosion).
Fin.castLEOrderEmb
Given n ≤ m, the canonical order-preserving embedding from Fin n into Fin m.
Set.mem_empty_iff_false
An element belongs to the empty set if and only if False.
iff_false
A proposition p is equivalent to False if and only if ¬p holds.
graph_11_mutual_visibility_chromatic_number_eq_three_empty_is_mutual_visibility_set
The empty set of vertices is a mutual-visibility set in any simple graph G.
graph_11_chromatic_number
The chromatic number of G_11 is 3.
graph_11_diam
The diameter of G_11 is 2.
graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two
For any finite graph with diameter 2, the mutual-visibility chromatic number is at most the chromatic number.
le_iInf
An element a is bounded above by the infimum of a family f if and only if a ≤ f(i) for all indices i.
graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono
If a graph G is mutual-visibility n-colorable and n ≤ m, then G is mutual-visibility m-colorable.
graph_11_not_is_mutual_visibility_colorable_two
The graph G_11 is not mutual-visibility 2-colorable.
le_antisymm
In any partial order, if a ≤ b and b ≤ a, then a = b.

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

lemma graph_11_mutual_visibility_chromatic_number_eq_three_empty_is_mutual_visibility_set    {V : Type*} (G : SimpleGraph V) :    graph_is_mutual_visibility_set G ∅ := by  intro u hu  exact False.elim hulemma graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono    {V : Type*} (G : SimpleGraph V) {n m : ℕ} (hnm : n ≤ m)    (hc : graph_is_mutual_visibility_colorable G n) :    graph_is_mutual_visibility_colorable G m := by  obtain ⟨c, hc⟩ := hc  let emb : Fin n ↪ Fin m := (Fin.castLEOrderEmb hnm).toEmbedding  use fun v => emb (c v)  intro i  by_cases hi : ∃ j : Fin n, emb j = i  · rcases hi with ⟨j, rfl⟩    have : {v | emb (c v) = emb j} = {v | c v = j} := by      ext v      simp [emb.injective.eq_iff]    rw [this]    exact hc j  · have : {v | emb (c v) = i} = ∅ := by      ext v      simp only [Set.mem_empty_iff_false, iff_false]      intro h_eq      exact hi ⟨c v, h_eq⟩    rw [this]    exact graph_11_mutual_visibility_chromatic_number_eq_three_empty_is_mutual_visibility_set G/-- The mutual-visibility chromatic number of G_11 is 3. -/theorem graph_11_mutual_visibility_chromatic_number_eq_three :    graph_mutual_visibility_chromatic_number graph_11 = 3 ∧    graph_11.chromaticNumber = 3 ∧    graph_11.diam = 2 := by  refine ⟨?_, graph_11_chromatic_number, graph_11_diam⟩  have hle : graph_mutual_visibility_chromatic_number graph_11 ≤ 3 := by    have h := graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two graph_11 graph_11_diam    rw [graph_11_chromatic_number] at h    exact h  have hge : (3 : ℕ∞) ≤ graph_mutual_visibility_chromatic_number graph_11 := by    dsimp [graph_mutual_visibility_chromatic_number]    apply le_iInf    intro n    apply le_iInf    intro hn    change graph_is_mutual_visibility_colorable graph_11 n at hn    by_contra! hlt    have hle2 : n ≤ 2 := by      norm_cast at hlt      omega    have h2 : graph_is_mutual_visibility_colorable graph_11 2 :=      graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono graph_11 hle2 hn    exact graph_11_not_is_mutual_visibility_colorable_two h2  exact le_antisymm hle hge
See it in the graphDiscuss this resultChallenge it