AFTD Auto-Formalizing Theoretical Domains

exists_diameter_two_graph_mutual_visibility_chromatic_number_three

theoremverifiedformalization

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

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.

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

    lines 7–9

    uses SimpleGraph.connected_iff_diam_ne_zero.2, graph_11_diam, graph_11_mutual_visibility_chromatic_number_eq_three.1, graph_11_chromatic_number

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

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

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