graph_11_mutual_visibility_chromatic_number_eq_three
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
- graph_11The 11-vertex simple graph G_11 on Fin 11 consisting of a base 4-cycle 0-1-2-3-0, four caps 4, 5, 6, 7 adjacent to consecutive base pairs,…
- graph_11_diamThe simple graph G_11 has diameter 2.
- graph_11_chromatic_numberThe chromatic number of the simple graph G_11 equals 3.
- graph_11_not_is_mutual_visibility_colorable_twoThe simple graph G_11 is not mutual-visibility 2-colorable.
- graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_twoFor every finite simple graph G of diameter 2, the mutual-visibility chromatic number of G is at most the chromatic number of G.
- graph_is_mutual_visibility_colorableA simple graph G is mutual-visibility n-colorable if there exists a coloring of the vertices of G with n colors such that every color…
- graph_is_mutual_visibility_setA set S of vertices of a simple graph G is a mutual-visibility set if for every pair of vertices u, v in S, there exists a shortest walk…
- graph_mutual_visibility_chromatic_numberThe mutual-visibility chromatic number of a simple graph G is the infimum in ℕ∞ of the natural numbers n such that G is mutual-visibility…
- Used by 1
- exists_diameter_two_graph_mutual_visibility_chromatic_number_threeThere exists a finite connected simple graph G of diameter 2 such that the mutual-visibility chromatic number of G equals 3 and the…
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.
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.
uses
False.elimintro u hu exact False.elim hu
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.
uses
Fin.castLEOrderEmbobtain ⟨c, hc⟩ := hc let emb : Fin n ↪ Fin m := (Fin.castLEOrderEmb hnm).toEmbedding use fun v => emb (c v)
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.
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
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.
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
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.
uses
graph_11_chromatic_number,graph_11_diamrefine ⟨?_, graph_11_chromatic_number, graph_11_diam⟩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.
uses
graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two,graph_11_diam,graph_11_chromatic_numberhave 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
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.
uses
le_iInfhave 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
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.
uses
graph_11_mutual_visibility_chromatic_number_eq_three_colorable_mono,graph_11_not_is_mutual_visibility_colorable_twoby_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 h2The 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.
uses
le_antisymmexact 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.
- The helper lemma establishing that the empty set is a mutual-visibility set is a formal requirement for extending colorings to larger target sets by adding empty color classes, a technical detail usually taken for granted on paper.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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