exists_diameter_two_graph_mutual_visibility_chromatic_number_three
There exists a finite connected simple graph G of diameter 2 such that the mutual-visibility chromatic number of G equals 3 and the chromatic number of G equals 3.
Statement
theorem exists_diameter_two_graph_mutual_visibility_chromatic_number_three : ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V) (_ : DecidableRel G.Adj), G.Connected ∧ G.diam = 2 ∧ graph_mutual_visibility_chromatic_number G = 3 ∧ G.chromaticNumber = 3
- Formalizes
- arXiv:2610.39430, Theorem 3.4
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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_mutual_visibility_chromatic_number_eq_threeThe simple graph G_11 has mutual-visibility chromatic number 3, chromatic number 3, and diameter 2.
Read back from the Lean
There exists a finite type $V$ and a simple graph $G$ on $V$ with decidable adjacency such that: 1. $G$ is connected, 2. the diameter of $G$ equals 2, 3. the mutual-visibility chromatic number of $G$ equals 3, and 4. the standard chromatic number of $G$ equals 3.
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 theorem is proved by exhibiting an explicit witness: the 11-vertex graph `graph_11` on `Fin 11`. Its diameter, mutual-visibility chromatic number, and chromatic number are supplied directly by previously established theorems about `graph_11`, and connectedness follows from its diameter being non-zero.
The explicit 11-vertex graph graph_11 satisfies all four conditions: it is connected, has diameter 2, has mutual-visibility chromatic number 3, and has chromatic number 3.
The existential statement is proved by providing the concrete graph `graph_11` on the vertex type `Fin 11` (which is finite by instance inference) and equipping it with classical decidability of adjacency (`Classical.decRel`). The four conjunctions are established as follows: - Connectedness: by `SimpleGraph.connected_iff_diam_ne_zero.2`, it suffices to show that the diameter is non-zero; rewriting with `graph_11_diam` reduces this to 2 ≠ 0, which is closed by numerical evaluation (`norm_num`). - Diameter: directly provided by the lemma `graph_11_diam`, which states that the diameter is 2. - Mutual-visibility chromatic number: provided by the first component of `graph_11_mutual_visibility_chromatic_number_eq_three.1`, stating that the mutual-visibility chromatic number is 3. - Chromatic number: directly provided by `graph_11_chromatic_number`, stating that the chromatic number is 3.
uses
SimpleGraph.connected_iff_diam_ne_zero.2,graph_11_diam,graph_11_mutual_visibility_chromatic_number_eq_three.1,graph_11_chromatic_numberrefine ⟨Fin 11, inferInstance, graph_11, Classical.decRel _, SimpleGraph.connected_iff_diam_ne_zero.2 (by rw [graph_11_diam]; norm_num), graph_11_diam, graph_11_mutual_visibility_chromatic_number_eq_three.1, graph_11_chromatic_number⟩
SimpleGraph.connected_iff_diam_ne_zero.2- A finite graph with non-zero diameter is connected.
graph_11_diam- The diameter of graph_11 is equal to 2.
graph_11_mutual_visibility_chromatic_number_eq_three.1- The mutual-visibility chromatic number of graph_11 is equal to 3.
graph_11_chromatic_number- The chromatic number of graph_11 is equal to 3.
- The adjacency relation is made decidable using classical logic (`Classical.decRel`), as required by the existential quantification, rather than by an explicit decision algorithm.
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.
/-- Existence of a diameter-two graph with mutual-visibility chromatic number and chromatic number both equal to 3. -/theorem exists_diameter_two_graph_mutual_visibility_chromatic_number_three : ∃ (V : Type) (_ : Fintype V) (G : SimpleGraph V) (_ : DecidableRel G.Adj), G.Connected ∧ G.diam = 2 ∧ graph_mutual_visibility_chromatic_number G = 3 ∧ G.chromaticNumber = 3 := by refine ⟨Fin 11, inferInstance, graph_11, Classical.decRel _, SimpleGraph.connected_iff_diam_ne_zero.2 (by rw [graph_11_diam]; norm_num), graph_11_diam, graph_11_mutual_visibility_chromatic_number_eq_three.1, graph_11_chromatic_number⟩