AFTD Auto-Formalizing Theoretical Domains

graph_11_diam

theoremverifiedformalization

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

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.

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

    lines 18–19

    uses Bool.and_eq_true, beq_iff_eq, bne_iff_ne, ne_eq, Bool.or_eq_true, or_assoc

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

    line 26

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

    lines 29–31

    uses SimpleGraph.edist_self, bot_le

      by_cases huv : u = v
      · rw [huv, SimpleGraph.edist_self]
        exact bot_le
  4. 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.

    lines 32–34

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

    lines 35–38

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

    lines 41–44

    uses not_le, le_top, Nat.cast_le.mpr, Nat.succ_le_of_lt, Nat.cast_lt.mp

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

    lines 47–52

    uses graph_11_diam_enat_two_le_of_not_le_one, SimpleGraph.edist_le_one_iff_adj_or_eq

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

    lines 56–59

    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_ediam

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

    lines 60–61

    uses SimpleGraph.diam

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

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

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