graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two
For every finite simple graph G of diameter 2, the mutual-visibility chromatic number of G is at most the chromatic number of G.
Statement
theorem graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two {V : Type*} [Fintype V] (G : SimpleGraph V) (hdiam : G.diam = 2) : graph_mutual_visibility_chromatic_number G ≤ G.chromaticNumber
- Formalizes
- arXiv:2610.39430, Proposition 1.2
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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…
- Used by 1
- 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
For any finite type $V$ and any simple graph $G$ on $V$, if the diameter of $G$ is equal to 2, then the mutual-visibility chromatic number of $G$ is less than or equal to the chromatic number of $G$ (both taking values in ℕ∞).
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 proof establishes that in any finite simple graph of diameter 2, every independent set is a mutual-visibility set. Indeed, any two distinct vertices in an independent set are non-adjacent, hence at distance exactly 2, and the intermediate vertex on a shortest walk between them cannot belong to the set without violating independence. Consequently, every proper graph coloring is also a mutual-visibility coloring because its color classes are independent sets, and the inequality χ_μ(G) ≤ χ(G) follows by taking the infimum over all admissible numbers of colors.
The graph G is nontrivial, connected, and has finite extended diameter.
Since the diameter of G is 2, it is non-zero. In a simple graph, a non-zero diameter implies the vertex type is nontrivial, the graph is connected, and the extended diameter is finite (not top).
have hne : G.diam ≠ 0 := by rw [hdiam]; decide have : Nontrivial V := G.nontrivial_of_diam_ne_zero hne have hconn : G.Connected := G.connected_iff_diam_ne_zero.mpr hne have hediam : G.ediam ≠ ⊤ := G.ediam_ne_top_of_diam_ne_zero hne
For any vertex u in S, the mutual-visibility condition holds for the pair (u, u).
Let u, v ∈ S. If u = v, the trivial walk from u to u has length 0, matching the distance d(u, u) = 0. Its vertex support contains only u, so every vertex on the walk in S is trivially equal to u or v.
uses
SimpleGraph.Walk.nil,SimpleGraph.Walk.support_nil,List.mem_singleton,Or.inlintro u hu v hv by_cases huv : u = v · subst huv use SimpleGraph.Walk.nil refine ⟨by simp, ?_⟩ intro x hx _ simp only [SimpleGraph.Walk.support_nil, List.mem_singleton] at hx exact Or.inl hx
Any two distinct vertices u, v in S have distance 2, and there exists a walk between them of length 2.
When u ≠ v, the assumption that S is independent implies u and v are not adjacent, so d(u, v) > 1. Since the diameter of G is 2, d(u, v) ≤ 2, forcing d(u, v) = 2. Because G is connected, there exists a walk p between u and v whose length equals this distance.
· have hnotadj : ¬ G.Adj u v := hS u v hu hv have hdist_le : G.dist u v ≤ 2 := by have := G.dist_le_diam hediam (u := u) (v := v) rwa [hdiam] at this have hdist_gt : 1 < G.dist u v := hconn.one_lt_dist_of_ne_of_not_adj huv hnotadj have hdist_eq : G.dist u v = 2 := by omega obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist u v have hp_len : p.length = 2 := hp.trans hdist_eq
The walk p decomposes into a path of two edges, u - w and w - v, through an intermediate vertex w.
By exhaustive structural case analysis on the walk p, walks of length 0, 1, or at least 3 are ruled out because p has length 2. Thus p must consist of an edge from u to some vertex w followed by an edge from w to v.
uses
SimpleGraph.Walk.length_cons,SimpleGraph.Walk.length_nilobtain ⟨w, h1, h2, hp_eq⟩ : ∃ (w : V) (h1 : G.Adj u w) (h2 : G.Adj w v), p = SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2 SimpleGraph.Walk.nil) := by cases p with | nil => contradiction | cons h1 p1 => cases p1 with | nil => simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at hp_len contradiction | cons h2 p2 => cases p2 with | nil => exact ⟨_, h1, h2, rfl⟩ | cons h3 p3 => simp only [SimpleGraph.Walk.length_cons] at hp_len omega subst hp_eq
The two-edge walk witnesses that S satisfies the mutual-visibility condition for u and v.
The vertices on the walk are u, w, and v. If the intermediate vertex w belonged to S, it would be adjacent to u ∈ S, contradicting that S is independent. Therefore, any vertex on the walk that lies in S must be u or v.
uses
SimpleGraph.Walk.support_cons,SimpleGraph.Walk.support_nil,List.mem_cons,List.not_mem_nil,or_false,Or.inl,Or.inrrefine ⟨_, hp, ?_⟩ intro x hx hxS simp only [SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with hxu | hxw | hxv · exact Or.inl hxu · have hx_adj : G.Adj u x := hxw ▸ h1 have hnot : ¬ G.Adj u x := hS u x hu hxS exact (hnot hx_adj).elim · exact Or.inr hxv
Every proper n-coloring of G is a mutual-visibility n-coloring.
Given a proper coloring c with n colors, no two adjacent vertices have the same color. Thus each color class {v | c(v) = i} is an independent set. By the first lemma, every independent set in a graph of diameter 2 is a mutual-visibility set, so c is a mutual-visibility coloring.
uses
graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_is_mutual_visibility_set_of_indepobtain ⟨c⟩ := hc refine ⟨c, fun i ↦ ?_⟩ apply graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_is_mutual_visibility_set_of_indep G hdiam intro u v hu hv hadj have hcu : c u = i := hu have hcv : c v = i := hv have hne : c u ≠ c v := c.valid hadj rw [hcu, hcv] at hne exact hne rfl
The mutual-visibility chromatic number of G is at most the chromatic number of G.
The mutual-visibility chromatic number and the chromatic number are the infima of the set of integers n for which G admits a mutual-visibility n-coloring and a proper n-coloring, respectively. Since every proper n-coloring is a mutual-visibility n-coloring, the set of colorable numbers is contained in the set of mutual-visibility colorable numbers. By monotonicity of the infimum (biInf_mono), χ_μ(G) ≤ χ(G).
uses
biInf_mono,graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_mv_colorable_of_colorablechange (⨅ n ∈ {n : ℕ | graph_is_mutual_visibility_colorable G n}, (n : ℕ∞)) ≤ ⨅ n ∈ Set.ofPred G.Colorable, (n : ℕ∞) apply biInf_mono intro n hn exact graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_mv_colorable_of_colorable G hdiam hn
SimpleGraph.Walk.nil- The empty walk from a vertex to itself, having length 0.
SimpleGraph.Walk.support_nil- The vertex sequence of the trivial walk at a vertex u is the singleton list [u].
List.mem_singleton- An element belongs to a singleton list [b] if and only if it equals b.
Or.inl- Given a proof of P, proves the disjunction P ∨ Q.
SimpleGraph.Walk.length_cons- The length of a walk formed by prepending an edge is one plus the length of the tail walk.
SimpleGraph.Walk.length_nil- The length of the trivial walk is 0.
SimpleGraph.Walk.support_cons- The vertex sequence of a walk formed by prepending an edge from u to v prepends u to the vertex sequence of the tail walk.
List.mem_cons- An element belongs to b :: l if and only if it equals b or belongs to l.
List.not_mem_nil- No element belongs to the empty list.
or_false- For any proposition P, P ∨ False is logically equivalent to P.
Or.inr- Given a proof of Q, proves the disjunction P ∨ Q.
graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_is_mutual_visibility_set_of_indep- In a finite simple graph of diameter 2, every independent set of vertices is a mutual-visibility set.
biInf_mono- If a predicate P implies Q, then the infimum over elements satisfying Q is at most the infimum over elements satisfying P.
graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_mv_colorable_of_colorable- In a finite simple graph of diameter 2, any proper n-coloring is a mutual-visibility n-coloring.
- The formal proof decomposes a walk of length 2 by explicit case analysis on the inductive walk constructor `SimpleGraph.Walk.cons`, ruling out walks of length 0, 1, or at least 3, whereas on paper one simply takes a path of two edges $u - w - v$.
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_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_is_mutual_visibility_set_of_indep {V : Type*} [Fintype V] (G : SimpleGraph V) (hdiam : G.diam = 2) (S : Set V) (hS : ∀ u v, u ∈ S → v ∈ S → ¬ G.Adj u v) : graph_is_mutual_visibility_set G S := by have hne : G.diam ≠ 0 := by rw [hdiam]; decide have : Nontrivial V := G.nontrivial_of_diam_ne_zero hne have hconn : G.Connected := G.connected_iff_diam_ne_zero.mpr hne have hediam : G.ediam ≠ ⊤ := G.ediam_ne_top_of_diam_ne_zero hne intro u hu v hv by_cases huv : u = v · subst huv use SimpleGraph.Walk.nil refine ⟨by simp, ?_⟩ intro x hx _ simp only [SimpleGraph.Walk.support_nil, List.mem_singleton] at hx exact Or.inl hx · have hnotadj : ¬ G.Adj u v := hS u v hu hv have hdist_le : G.dist u v ≤ 2 := by have := G.dist_le_diam hediam (u := u) (v := v) rwa [hdiam] at this have hdist_gt : 1 < G.dist u v := hconn.one_lt_dist_of_ne_of_not_adj huv hnotadj have hdist_eq : G.dist u v = 2 := by omega obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist u v have hp_len : p.length = 2 := hp.trans hdist_eq obtain ⟨w, h1, h2, hp_eq⟩ : ∃ (w : V) (h1 : G.Adj u w) (h2 : G.Adj w v), p = SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2 SimpleGraph.Walk.nil) := by cases p with | nil => contradiction | cons h1 p1 => cases p1 with | nil => simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at hp_len contradiction | cons h2 p2 => cases p2 with | nil => exact ⟨_, h1, h2, rfl⟩ | cons h3 p3 => simp only [SimpleGraph.Walk.length_cons] at hp_len omega subst hp_eq refine ⟨_, hp, ?_⟩ intro x hx hxS simp only [SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with hxu | hxw | hxv · exact Or.inl hxu · have hx_adj : G.Adj u x := hxw ▸ h1 have hnot : ¬ G.Adj u x := hS u x hu hxS exact (hnot hx_adj).elim · exact Or.inr hxvlemma graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_mv_colorable_of_colorable {V : Type*} [Fintype V] (G : SimpleGraph V) (hdiam : G.diam = 2) {n : ℕ} (hc : G.Colorable n) : graph_is_mutual_visibility_colorable G n := by obtain ⟨c⟩ := hc refine ⟨c, fun i ↦ ?_⟩ apply graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_is_mutual_visibility_set_of_indep G hdiam intro u v hu hv hadj have hcu : c u = i := hu have hcv : c v = i := hv have hne : c u ≠ c v := c.valid hadj rw [hcu, hcv] at hne exact hne rfl/-- In any finite diameter-2 graph, χ_μ(G) ≤ χ(G). -/theorem graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two {V : Type*} [Fintype V] (G : SimpleGraph V) (hdiam : G.diam = 2) : graph_mutual_visibility_chromatic_number G ≤ G.chromaticNumber := by change (⨅ n ∈ {n : ℕ | graph_is_mutual_visibility_colorable G n}, (n : ℕ∞)) ≤ ⨅ n ∈ Set.ofPred G.Colorable, (n : ℕ∞) apply biInf_mono intro n hn exact graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_mv_colorable_of_colorable G hdiam hn