graph_11_diam
The simple graph G_11 has diameter 2.
Statement
theorem graph_11_diam : graph_11.diam = 2- Formalizes
- arXiv:2610.39430 Lemma 3.3
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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,…
- Used by 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.
- graph_11_not_is_mutual_visibility_colorable_twoThe simple graph G_11 is not mutual-visibility 2-colorable.
- 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
The diameter of the simple graph graph_11 (with vertex set Fin 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 proof computes the diameter of the 11-vertex graph G₁₁ by showing that its extended diameter is 2. The upper bound ediam ≤ 2 follows because identical vertices have distance 0, adjacent vertices have distance 1, and every pair of distinct non-adjacent vertices shares a common neighbor (checked by finite exhaustion), yielding distance at most 2 by the triangle inequality. The lower bound ediam ≥ 2 follows by exhibiting the pair (0, 2), which are neither equal nor adjacent and hence have distance at least 2.
The boolean adjacency test graph_11_diam_adj_b u v evaluates to true if and only if u and v are adjacent in G₁₁.
We unfold the definitions of the boolean functions and graph_11, then simplify boolean operators to their propositional counterparts, matching the relational definition of G₁₁.
uses
Bool.and_eq_true,beq_iff_eq,bne_iff_ne,ne_eq,Bool.or_eq_true,or_assocdsimp [graph_11_diam_adj_b, graph_11_diam_b, graph_11, SimpleGraph.fromRel] simp only [Bool.and_eq_true, beq_iff_eq, bne_iff_ne, ne_eq, Bool.or_eq_true, or_assoc]
Every pair of distinct, non-adjacent vertices in G₁₁ has a common neighbor. automation
Since G₁₁ is finite and adjacency is decidable, the assertion is a finite universal quantifier over Fin 11 × Fin 11, which Lean checks by exhaustive computation.
decideIf u = v, the extended distance between u and v is at most 2.
When u = v, the distance from a vertex to itself is 0, and 0 ≤ 2.
uses
SimpleGraph.edist_self,bot_leby_cases huv : u = v · rw [huv, SimpleGraph.edist_self] exact bot_le
If u ≠ v and u is adjacent to v, the extended distance between u and v is at most 2.
Adjacency implies the extended distance is 1, and 1 ≤ 2.
uses
SimpleGraph.edist_eq_one_iff_adj.mpr,one_le_two· by_cases hadj : graph_11.Adj u v · rw [SimpleGraph.edist_eq_one_iff_adj.mpr hadj] exact one_le_two
If u ≠ v and u is not adjacent to v, the extended distance between u and v is at most 2.
By the common neighbor lemma, there exists a vertex w adjacent to both u and v. By the triangle inequality, the distance from u to v is at most the sum of the distances from u to w and w to v, which is 1 + 1 = 2.
uses
graph_11_diam_common_neighbor,graph_11.edist_triangle,SimpleGraph.edist_eq_one_iff_adj.mpr· obtain ⟨w, hw1, hw2⟩ := graph_11_diam_common_neighbor u v huv hadj have ht := graph_11.edist_triangle (u := u) (v := w) (w := v) rw [SimpleGraph.edist_eq_one_iff_adj.mpr hw1, SimpleGraph.edist_eq_one_iff_adj.mpr hw2] at ht exact ht
For any extended natural number x, if ¬(x ≤ 1), then 2 ≤ x.
Negating x ≤ 1 yields 1 < x. If x is ⊤, 2 ≤ ⊤ holds trivially; if x is a finite natural number n, 1 < n implies n ≥ 2.
uses
not_le,le_top,Nat.cast_le.mpr,Nat.succ_le_of_lt,Nat.cast_lt.mprw [not_le] at h cases x with | top => exact le_top | coe n => exact Nat.cast_le.mpr (Nat.succ_le_of_lt (Nat.cast_lt.mp h))
The extended distance between vertex 0 and vertex 2 is at least 2. automation
By the preceding lemma, it suffices to refute edist 0 2 ≤ 1. A distance of at most 1 would mean vertices 0 and 2 are adjacent or equal; both possibilities are refuted by finite computation using decide.
uses
graph_11_diam_enat_two_le_of_not_le_one,SimpleGraph.edist_le_one_iff_adj_or_eqapply graph_11_diam_enat_two_le_of_not_le_one intro h rw [SimpleGraph.edist_le_one_iff_adj_or_eq] at h rcases h with h | h · revert h; decide · revert h; decide
The extended diameter of G₁₁ is 2.
By antisymmetry: since every pairwise distance is at most 2, ediam ≤ 2; and since edist 0 2 ≥ 2 and any pairwise distance bounds the diameter from below, ediam ≥ 2.
uses
le_antisymm,SimpleGraph.ediam_le_of_edist_le,graph_11_diam_edist_le_two,le_trans,graph_11_diam_edist_0_2_ge_two,SimpleGraph.edist_le_ediamhave hediam : graph_11.ediam = 2 := by apply le_antisymm · exact SimpleGraph.ediam_le_of_edist_le graph_11_diam_edist_le_two · exact le_trans graph_11_diam_edist_0_2_ge_two SimpleGraph.edist_le_ediam
The diameter of G₁₁ is 2.
The diameter diam is defined as the natural number cast of ediam. Substituting ediam = 2 and evaluating the conversion gives 2.
uses
SimpleGraph.diamrw [SimpleGraph.diam, hediam] rfl
Bool.and_eq_true- A boolean conjunction evaluates to true if and only if both operands are true.
Bool.or_eq_true- A boolean disjunction evaluates to true if and only if at least one operand is true.
beq_iff_eq- Boolean equality evaluates to true if and only if the arguments are propositionally equal.
bne_iff_ne- Boolean inequality evaluates to true if and only if the arguments are distinct.
ne_eq- The proposition a ≠ b is definitionally ¬(a = b).
or_assoc- Disjunction of propositions is associative: (a ∨ b) ∨ c ↔ a ∨ (b ∨ c).
SimpleGraph.edist_self- The extended distance from any vertex to itself in a graph is 0.
bot_le- The bottom element of an order with a least element (here 0 in ℕ∞) is less than or equal to any element.
SimpleGraph.edist_eq_one_iff_adj.mpr- If two vertices in a graph are adjacent, the extended distance between them is 1.
one_le_two- In any ordered semiring, 1 ≤ 2.
graph_11_diam_common_neighbor- Any two distinct, non-adjacent vertices in G₁₁ share a common neighbor.
graph_11.edist_triangle- The triangle inequality for extended graph distance: the distance from u to w is at most the sum of distances from u to v and from v to w.
not_le- In a linear order, ¬(a ≤ b) is equivalent to b < a.
le_top- Any element of an order with a greatest element (such as ℕ∞) is less than or equal to ⊤.
Nat.cast_le.mpr- The canonical embedding from ℕ to ℕ∞ preserves the ≤ relation.
Nat.succ_le_of_lt- In ℕ, if n < m, then n + 1 ≤ m.
Nat.cast_lt.mp- The canonical embedding from ℕ to ℕ∞ reflects strict inequality.
graph_11_diam_enat_two_le_of_not_le_one- In ℕ∞, if x is not at most 1, then 2 ≤ x.
SimpleGraph.edist_le_one_iff_adj_or_eq- The extended distance between two vertices is at most 1 if and only if they are adjacent or equal.
le_antisymm- In a partial order, a ≤ b and b ≤ a together imply a = b.
SimpleGraph.ediam_le_of_edist_le- If the extended distance between every pair of vertices is at most k, then the extended diameter is at most k.
graph_11_diam_edist_le_two- The extended distance between any two vertices in G₁₁ is at most 2.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
graph_11_diam_edist_0_2_ge_two- The extended distance between vertex 0 and vertex 2 in G₁₁ is at least 2.
SimpleGraph.edist_le_ediam- The extended distance between any pair of vertices is bounded above by the graph's extended diameter.
SimpleGraph.diam- The diameter of a graph in ℕ is defined as the extended diameter converted to a natural number.
- Adjacency in G₁₁ is decidable via a boolean decision function (graph_11_diam_adj_b), enabling Lean's decide tactic to check graph properties by finite case exhaustion.
- The existence of a common neighbor for all distinct non-adjacent pairs (graph_11_diam_common_neighbor) is verified entirely by decide, checking all 121 vertex pairs automatically.
- The diameter is defined in Mathlib via the extended natural numbers ℕ∞ (ediam), so the proof first establishes ediam = 2 using extended distances and then evaluates diam = ediam.toNat = 2.
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.
def graph_11_diam_b (u v : Fin 11) : Bool := (u == 0 && v == 1) || (u == 1 && v == 2) || (u == 2 && v == 3) || (u == 3 && v == 0) || (u == 4 && (v == 0 || v == 1)) || (u == 5 && (v == 1 || v == 2)) || (u == 6 && (v == 2 || v == 3)) || (u == 7 && (v == 3 || v == 0)) || (u == 8 && (v == 4 || v == 6)) || (u == 9 && (v == 5 || v == 7)) || (u == 10 && (v == 4 || v == 5 || v == 6 || v == 7 || v == 8 || v == 9))def graph_11_diam_adj_b (u v : Fin 11) : Bool := (u != v) && (graph_11_diam_b u v || graph_11_diam_b v u)lemma graph_11_diam_adj_b_iff (u v : Fin 11) : graph_11_diam_adj_b u v = true ↔ graph_11.Adj u v := by dsimp [graph_11_diam_adj_b, graph_11_diam_b, graph_11, SimpleGraph.fromRel] simp only [Bool.and_eq_true, beq_iff_eq, bne_iff_ne, ne_eq, Bool.or_eq_true, or_assoc]instance graph_11_diam_decidableAdj : DecidableRel graph_11.Adj := fun u v => decidable_of_iff (graph_11_diam_adj_b u v = true) (graph_11_diam_adj_b_iff u v)lemma graph_11_diam_common_neighbor : ∀ u v : Fin 11, u ≠ v → ¬ graph_11.Adj u v → ∃ w, graph_11.Adj u w ∧ graph_11.Adj w v := by decidelemma graph_11_diam_edist_le_two (u v : Fin 11) : graph_11.edist u v ≤ 2 := by by_cases huv : u = v · rw [huv, SimpleGraph.edist_self] exact bot_le · by_cases hadj : graph_11.Adj u v · rw [SimpleGraph.edist_eq_one_iff_adj.mpr hadj] exact one_le_two · obtain ⟨w, hw1, hw2⟩ := graph_11_diam_common_neighbor u v huv hadj have ht := graph_11.edist_triangle (u := u) (v := w) (w := v) rw [SimpleGraph.edist_eq_one_iff_adj.mpr hw1, SimpleGraph.edist_eq_one_iff_adj.mpr hw2] at ht exact htlemma graph_11_diam_enat_two_le_of_not_le_one {x : ℕ∞} (h : ¬ (x ≤ 1)) : 2 ≤ x := by rw [not_le] at h cases x with | top => exact le_top | coe n => exact Nat.cast_le.mpr (Nat.succ_le_of_lt (Nat.cast_lt.mp h))lemma graph_11_diam_edist_0_2_ge_two : 2 ≤ graph_11.edist 0 2 := by apply graph_11_diam_enat_two_le_of_not_le_one intro h rw [SimpleGraph.edist_le_one_iff_adj_or_eq] at h rcases h with h | h · revert h; decide · revert h; decide/-- The simple graph G_11 has diameter 2. -/theorem graph_11_diam : graph_11.diam = 2 := by have hediam : graph_11.ediam = 2 := by apply le_antisymm · exact SimpleGraph.ediam_le_of_edist_le graph_11_diam_edist_le_two · exact le_trans graph_11_diam_edist_0_2_ge_two SimpleGraph.edist_le_ediam rw [SimpleGraph.diam, hediam] rfl