AFTD Auto-Formalizing Theoretical Domains

graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two

theoremverifiedformalization

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
Used by 1

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.

  1. 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).

    lines 5–8

      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
  2. 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.

    lines 9–16

    uses SimpleGraph.Walk.nil, SimpleGraph.Walk.support_nil, List.mem_singleton, Or.inl

      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
  3. 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.

    lines 17–24

      · 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
  4. 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.

    lines 25–40

    uses SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil

        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
  5. 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.

    lines 41–50

    uses SimpleGraph.Walk.support_cons, SimpleGraph.Walk.support_nil, List.mem_cons, List.not_mem_nil, or_false, Or.inl, Or.inr

        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 hxv
  6. 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.

    lines 56–64

    uses graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_is_mutual_visibility_set_of_indep

      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
  7. 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).

    lines 70–74

    uses biInf_mono, graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_two_mv_colorable_of_colorable

      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
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.

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_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
See it in the graphDiscuss this resultChallenge it