AFTD Auto-Formalizing Theoretical Domains

cycle_seven_diam_eq_three

theoremverified

The diameter of the 7-cycle graph C_7 is equal to 3.

Statement

theorem cycle_seven_diam_eq_three : (SimpleGraph.cycleGraph 7).diam = 3
Source
folklore; OP-537
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

Read back from the Lean

The diameter of the cycle graph on 7 vertices (SimpleGraph.cycleGraph 7) is equal to 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 diameter of the 7-cycle graph C_7 is 3. To prove this, the argument first establishes the upper bound by bounding the distance from any vertex u to u + d for each d ∈ {0, ..., 6} in Fin 7: forward distances d ∈ {1, 2, 3} are bounded by d using the triangle inequality, while wrap-around distances d ∈ {4, 5, 6} are rewritten as backward steps u - (7 - d), ensuring every pair has distance at most 3. For the lower bound, the pair of vertices 0 and 3 is shown to have distance strictly greater than 2 by verifying they are distinct, non-adjacent, and share no common neighbors. Combining the upper and lower bounds on the extended diameter determines that the diameter is exactly 3.

  1. Every vertex in the 7-cycle graph is adjacent to its successor and predecessor.

    By definition of the cycle graph on Fin 7, two vertices u and v are adjacent if and only if u - v = 1 or v - u = 1. For u + 1, (u + 1) - u simplifies to 1, providing the right disjunct via Or.inr. For u - 1, u - (u - 1) simplifies to 1, providing the left disjunct via Or.inl.

    lines 1–8

    uses Or.inr, Or.inl

    private def cycle_seven_diam_eq_three_G : SimpleGraph (Fin 7) := SimpleGraph.cycleGraph 7
    
    private lemma cycle_seven_diam_eq_three_adj_add_one (u : Fin 7) :
        cycle_seven_diam_eq_three_G.Adj u (u + 1) := Or.inr (by simp)
    
    private lemma cycle_seven_diam_eq_three_adj_sub_one (u : Fin 7) :
        cycle_seven_diam_eq_three_G.Adj u (u - 1) := Or.inl (by simp)
    
  2. The graph distance from any vertex u to u + 1 or u - 1 is at most 1.

    Because u is adjacent to both u + 1 and u - 1, the lemma SimpleGraph.edist_eq_one_iff_adj.mpr rewrites both graph distances to 1, which trivially satisfies being at most 1.

    lines 9–16

    uses SimpleGraph.edist_eq_one_iff_adj.mpr

    private lemma cycle_seven_diam_eq_three_edist_add_one_le (u : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u (u + 1) ≤ 1 := by
      rw [SimpleGraph.edist_eq_one_iff_adj.mpr (cycle_seven_diam_eq_three_adj_add_one u)]
    
    private lemma cycle_seven_diam_eq_three_edist_sub_one_le (u : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u (u - 1) ≤ 1 := by
      rw [SimpleGraph.edist_eq_one_iff_adj.mpr (cycle_seven_diam_eq_three_adj_sub_one u)]
    
  3. The graph distance from u to u + 2 is at most 2, and from u to u + 3 is at most 3.

    Applying the triangle inequality (SimpleGraph.edist_triangle) through u + 1 bounds edist(u, u + 2) by edist(u, u + 1) + edist(u + 1, u + 2). Associativity of addition (add_assoc) identifies u + 2 with (u + 1) + 1, bounding the second step by 1 and the sum by 2. Repeating the triangle inequality through u + 2 similarly bounds edist(u, u + 3) by 2 + 1 = 3.

    lines 17–34

    uses SimpleGraph.edist_triangle, add_assoc, le_trans, add_le_add

    private lemma cycle_seven_diam_eq_three_edist_add_two_le (u : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u (u + 2) ≤ 2 := by
      have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u + 1) (u + 2)
      have h2 : cycle_seven_diam_eq_three_G.edist (u + 1) (u + 2) ≤ 1 := by
        have : u + 2 = (u + 1) + 1 := by rw [add_assoc]; rfl
        rw [this]
        exact cycle_seven_diam_eq_three_edist_add_one_le (u + 1)
      exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_add_one_le u) h2)
    
    private lemma cycle_seven_diam_eq_three_edist_add_three_le (u : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u (u + 3) ≤ 3 := by
      have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u + 2) (u + 3)
      have h2 : cycle_seven_diam_eq_three_G.edist (u + 2) (u + 3) ≤ 1 := by
        have : u + 3 = (u + 2) + 1 := by rw [add_assoc]; rfl
        rw [this]
        exact cycle_seven_diam_eq_three_edist_add_one_le (u + 2)
      exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_add_two_le u) h2)
    
  4. The graph distance from u to u - 2 is at most 2, and from u to u - 3 is at most 3.

    Analogous to the forward steps, the triangle inequality (SimpleGraph.edist_triangle) through u - 1 bounds edist(u, u - 2) by edist(u, u - 1) + edist(u - 1, u - 2). Rewriting u - 2 as (u - 1) - 1 via sub_sub bounds each step by 1 and the total by 2. Chaining a further step through u - 2 similarly bounds edist(u, u - 3) by 2 + 1 = 3.

    lines 35–52

    uses SimpleGraph.edist_triangle, sub_sub, le_trans, add_le_add

    private lemma cycle_seven_diam_eq_three_edist_sub_two_le (u : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u (u - 2) ≤ 2 := by
      have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u - 1) (u - 2)
      have h2 : cycle_seven_diam_eq_three_G.edist (u - 1) (u - 2) ≤ 1 := by
        have : u - 2 = (u - 1) - 1 := by rw [sub_sub]; rfl
        rw [this]
        exact cycle_seven_diam_eq_three_edist_sub_one_le (u - 1)
      exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_sub_one_le u) h2)
    
    private lemma cycle_seven_diam_eq_three_edist_sub_three_le (u : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u (u - 3) ≤ 3 := by
      have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u - 2) (u - 3)
      have h2 : cycle_seven_diam_eq_three_G.edist (u - 2) (u - 3) ≤ 1 := by
        have : u - 3 = (u - 2) - 1 := by rw [sub_sub]; rfl
        rw [this]
        exact cycle_seven_diam_eq_three_edist_sub_one_le (u - 2)
      exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_sub_two_le u) h2)
    
  5. The graph distance from u to u + 4, u + 5, and u + 6 is at most 3.

    In Fin 7, modular arithmetic (Fin.add_def, Fin.sub_def) shows that u + 4 = u - 3, so edist(u, u + 4) is at most 3 by the backward bound. Similarly, u + 5 = u - 2 gives a distance of at most 2 ≤ 3, and u + 6 = u - 1 gives a distance of at most 1 ≤ 3.

    lines 53–70

    uses Fin.add_def, Fin.sub_def, le_trans

    private lemma cycle_seven_diam_eq_three_edist_add_four_le (u : Fin 7) (h : 4 < 7) :
        cycle_seven_diam_eq_three_G.edist u (u + ⟨4, h⟩) ≤ 3 := by
      have : u + ⟨4, h⟩ = u - 3 := by ext; simp [Fin.add_def, Fin.sub_def]; omega
      rw [this]
      exact cycle_seven_diam_eq_three_edist_sub_three_le u
    
    private lemma cycle_seven_diam_eq_three_edist_add_five_le (u : Fin 7) (h : 5 < 7) :
        cycle_seven_diam_eq_three_G.edist u (u + ⟨5, h⟩) ≤ 3 := by
      have : u + ⟨5, h⟩ = u - 2 := by ext; simp [Fin.add_def, Fin.sub_def]; omega
      rw [this]
      exact le_trans (cycle_seven_diam_eq_three_edist_sub_two_le u) (by decide)
    
    private lemma cycle_seven_diam_eq_three_edist_add_six_le (u : Fin 7) (h : 6 < 7) :
        cycle_seven_diam_eq_three_G.edist u (u + ⟨6, h⟩) ≤ 3 := by
      have : u + ⟨6, h⟩ = u - 1 := by ext; simp [Fin.add_def, Fin.sub_def]; omega
      rw [this]
      exact le_trans (cycle_seven_diam_eq_three_edist_sub_one_le u) (by decide)
    
  6. The distance between any two vertices in the 7-cycle graph is at most 3.

    Any target vertex v can be expressed as u + d where d = v - u in Fin 7. A complete case split on d ∈ {0, 1, 2, 3, 4, 5, 6} covers all possibilities: d = 0 gives distance 0 ≤ 3, d ∈ {1, 2, 3} use the forward distance bounds, and d ∈ {4, 5, 6} use the backward wrap-around bounds.

    lines 71–84

    uses le_trans

    private lemma cycle_seven_diam_eq_three_edist_le_three (u v : Fin 7) :
        cycle_seven_diam_eq_three_G.edist u v ≤ 3 := by
      have h : v = u + (v - u) := by simp
      generalize hd : v - u = d
      rw [hd] at h
      fin_cases d
      · subst h; simp
      · subst h; dsimp only; exact le_trans (cycle_seven_diam_eq_three_edist_add_one_le u) (by decide)
      · subst h; dsimp only; exact le_trans (cycle_seven_diam_eq_three_edist_add_two_le u) (by decide)
      · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_three_le u
      · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_four_le u _
      · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_five_le u _
      · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_six_le u _
    
  7. The extended diameter of the 7-cycle graph is at most 3.

    Having shown that the distance between any two vertices u and v is at most 3, SimpleGraph.ediam_le_iff.mpr immediately implies that the extended diameter ediam is at most 3.

    lines 85–89

    uses SimpleGraph.ediam_le_iff.mpr

    /-- The diameter of the 7-cycle graph is 3. -/
    theorem cycle_seven_diam_eq_three : (SimpleGraph.cycleGraph 7).diam = 3 := by
      change cycle_seven_diam_eq_three_G.diam = 3
      have h_le : cycle_seven_diam_eq_three_G.ediam ≤ 3 :=
        SimpleGraph.ediam_le_iff.mpr cycle_seven_diam_eq_three_edist_le_three
  8. The distance between vertices 0 and 3 is strictly greater than 2.

    By finite check (decide), vertices 0 and 3 are distinct, non-adjacent, and have no common neighbors, so their common neighbor set is empty (Set.eq_empty_iff_forall_notMem). By SimpleGraph.two_lt_edist_iff, these three conditions are precisely equivalent to 2 < edist(0, 3).

    lines 90–99

    uses Set.eq_empty_iff_forall_notMem, SimpleGraph.two_lt_edist_iff

      have h_prop : (0 : Fin 7) ≠ 3 ∧ ¬ cycle_seven_diam_eq_three_G.Adj 0 3 ∧
          ∀ x, x ∉ cycle_seven_diam_eq_three_G.commonNeighbors 0 3 := by
        dsimp [cycle_seven_diam_eq_three_G]
        decide
      have h_empty : cycle_seven_diam_eq_three_G.commonNeighbors 0 3 = ∅ := by
        rw [Set.eq_empty_iff_forall_notMem]
        exact h_prop.2.2
      have h_lt : 2 < cycle_seven_diam_eq_three_G.edist 0 3 := by
        rw [SimpleGraph.two_lt_edist_iff]
        exact ⟨h_prop.1, h_prop.2.1, h_empty⟩
  9. The diameter of the 7-cycle graph is 3.

    From 2 < edist(0, 3), ENat.natCast_add_one_le_iff implies 3 ≤ edist(0, 3). Since any vertex distance is bounded by the extended diameter (SimpleGraph.edist_le_ediam), this gives 3 ≤ ediam. Combining this with the upper bound ediam ≤ 3 yields ediam = 3 by le_antisymm. Unfolding SimpleGraph.diam converts this extended natural number to the natural number 3.

    lines 100–108

    uses ENat.natCast_add_one_le_iff, le_trans, SimpleGraph.edist_le_ediam, le_antisymm, SimpleGraph.diam

      have h_ge_edist : 3 ≤ cycle_seven_diam_eq_three_G.edist 0 3 := by
        have h : (2 : ℕ) + 1 ≤ cycle_seven_diam_eq_three_G.edist 0 3 ↔ (2 : ℕ) < cycle_seven_diam_eq_three_G.edist 0 3 :=
          ENat.natCast_add_one_le_iff
        exact h.mpr h_lt
      have h_ge : 3 ≤ cycle_seven_diam_eq_three_G.ediam :=
        le_trans h_ge_edist SimpleGraph.edist_le_ediam
      have h_ediam : cycle_seven_diam_eq_three_G.ediam = 3 := le_antisymm h_le h_ge
      rw [SimpleGraph.diam, h_ediam]
      rfl
add_assoc
Addition in an additive semigroup is associative: (a + b) + c = a + (b + c).
add_le_add
Addition preserves inequalities: if a ≤ b and c ≤ d, then a + c ≤ b + d.
ENat.natCast_add_one_le_iff
In the extended natural numbers, m + 1 ≤ n if and only if m < n.
Fin.add_def
Addition in Fin n is computed by adding the underlying natural numbers modulo n.
Fin.sub_def
Subtraction in Fin n is computed by modular subtraction of the underlying natural numbers.
le_antisymm
Antisymmetry of order: if a ≤ b and b ≤ a, then a = b.
le_trans
Transitivity of the order relation: if a ≤ b and b ≤ c, then a ≤ c.
Or.inl
Given a proof of the left disjunct, concludes a ∨ b.
Or.inr
Given a proof of the right disjunct, concludes a ∨ b.
Set.eq_empty_iff_forall_notMem
A set is empty if and only if no element belongs to it.
SimpleGraph.diam
The graph diameter, defined as the extended diameter cast to a natural number via ENat.toNat.
SimpleGraph.ediam_le_iff.mpr
If the distance between every pair of vertices is at most d, then the extended diameter of the graph is at most d.
SimpleGraph.edist_eq_one_iff_adj.mpr
If two vertices in a graph are adjacent, their extended distance is 1.
SimpleGraph.edist_le_ediam
The extended distance between any two vertices is at most the extended diameter of the graph.
SimpleGraph.edist_triangle
The triangle inequality for extended graph distance: the distance from u to w is at most the distance from u to v plus the distance from v to w.
SimpleGraph.two_lt_edist_iff
The extended distance between vertices u and v is strictly greater than 2 if and only if u ≠ v, u and v are not adjacent, and they share no common neighbors.
sub_sub
Subtracting twice is equivalent to subtracting the sum: (a - b) - c = a - (b + c).

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

private def cycle_seven_diam_eq_three_G : SimpleGraph (Fin 7) := SimpleGraph.cycleGraph 7private lemma cycle_seven_diam_eq_three_adj_add_one (u : Fin 7) :    cycle_seven_diam_eq_three_G.Adj u (u + 1) := Or.inr (by simp)private lemma cycle_seven_diam_eq_three_adj_sub_one (u : Fin 7) :    cycle_seven_diam_eq_three_G.Adj u (u - 1) := Or.inl (by simp)private lemma cycle_seven_diam_eq_three_edist_add_one_le (u : Fin 7) :    cycle_seven_diam_eq_three_G.edist u (u + 1) ≤ 1 := by  rw [SimpleGraph.edist_eq_one_iff_adj.mpr (cycle_seven_diam_eq_three_adj_add_one u)]private lemma cycle_seven_diam_eq_three_edist_sub_one_le (u : Fin 7) :    cycle_seven_diam_eq_three_G.edist u (u - 1) ≤ 1 := by  rw [SimpleGraph.edist_eq_one_iff_adj.mpr (cycle_seven_diam_eq_three_adj_sub_one u)]private lemma cycle_seven_diam_eq_three_edist_add_two_le (u : Fin 7) :    cycle_seven_diam_eq_three_G.edist u (u + 2) ≤ 2 := by  have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u + 1) (u + 2)  have h2 : cycle_seven_diam_eq_three_G.edist (u + 1) (u + 2) ≤ 1 := by    have : u + 2 = (u + 1) + 1 := by rw [add_assoc]; rfl    rw [this]    exact cycle_seven_diam_eq_three_edist_add_one_le (u + 1)  exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_add_one_le u) h2)private lemma cycle_seven_diam_eq_three_edist_add_three_le (u : Fin 7) :    cycle_seven_diam_eq_three_G.edist u (u + 3) ≤ 3 := by  have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u + 2) (u + 3)  have h2 : cycle_seven_diam_eq_three_G.edist (u + 2) (u + 3) ≤ 1 := by    have : u + 3 = (u + 2) + 1 := by rw [add_assoc]; rfl    rw [this]    exact cycle_seven_diam_eq_three_edist_add_one_le (u + 2)  exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_add_two_le u) h2)private lemma cycle_seven_diam_eq_three_edist_sub_two_le (u : Fin 7) :    cycle_seven_diam_eq_three_G.edist u (u - 2) ≤ 2 := by  have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u - 1) (u - 2)  have h2 : cycle_seven_diam_eq_three_G.edist (u - 1) (u - 2) ≤ 1 := by    have : u - 2 = (u - 1) - 1 := by rw [sub_sub]; rfl    rw [this]    exact cycle_seven_diam_eq_three_edist_sub_one_le (u - 1)  exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_sub_one_le u) h2)private lemma cycle_seven_diam_eq_three_edist_sub_three_le (u : Fin 7) :    cycle_seven_diam_eq_three_G.edist u (u - 3) ≤ 3 := by  have ht := @SimpleGraph.edist_triangle _ cycle_seven_diam_eq_three_G u (u - 2) (u - 3)  have h2 : cycle_seven_diam_eq_three_G.edist (u - 2) (u - 3) ≤ 1 := by    have : u - 3 = (u - 2) - 1 := by rw [sub_sub]; rfl    rw [this]    exact cycle_seven_diam_eq_three_edist_sub_one_le (u - 2)  exact le_trans ht (add_le_add (cycle_seven_diam_eq_three_edist_sub_two_le u) h2)private lemma cycle_seven_diam_eq_three_edist_add_four_le (u : Fin 7) (h : 4 < 7) :    cycle_seven_diam_eq_three_G.edist u (u + ⟨4, h⟩) ≤ 3 := by  have : u + ⟨4, h⟩ = u - 3 := by ext; simp [Fin.add_def, Fin.sub_def]; omega  rw [this]  exact cycle_seven_diam_eq_three_edist_sub_three_le uprivate lemma cycle_seven_diam_eq_three_edist_add_five_le (u : Fin 7) (h : 5 < 7) :    cycle_seven_diam_eq_three_G.edist u (u + ⟨5, h⟩) ≤ 3 := by  have : u + ⟨5, h⟩ = u - 2 := by ext; simp [Fin.add_def, Fin.sub_def]; omega  rw [this]  exact le_trans (cycle_seven_diam_eq_three_edist_sub_two_le u) (by decide)private lemma cycle_seven_diam_eq_three_edist_add_six_le (u : Fin 7) (h : 6 < 7) :    cycle_seven_diam_eq_three_G.edist u (u + ⟨6, h⟩) ≤ 3 := by  have : u + ⟨6, h⟩ = u - 1 := by ext; simp [Fin.add_def, Fin.sub_def]; omega  rw [this]  exact le_trans (cycle_seven_diam_eq_three_edist_sub_one_le u) (by decide)private lemma cycle_seven_diam_eq_three_edist_le_three (u v : Fin 7) :    cycle_seven_diam_eq_three_G.edist u v ≤ 3 := by  have h : v = u + (v - u) := by simp  generalize hd : v - u = d  rw [hd] at h  fin_cases d  · subst h; simp  · subst h; dsimp only; exact le_trans (cycle_seven_diam_eq_three_edist_add_one_le u) (by decide)  · subst h; dsimp only; exact le_trans (cycle_seven_diam_eq_three_edist_add_two_le u) (by decide)  · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_three_le u  · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_four_le u _  · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_five_le u _  · subst h; dsimp only; exact cycle_seven_diam_eq_three_edist_add_six_le u _/-- The diameter of the 7-cycle graph is 3. -/theorem cycle_seven_diam_eq_three : (SimpleGraph.cycleGraph 7).diam = 3 := by  change cycle_seven_diam_eq_three_G.diam = 3  have h_le : cycle_seven_diam_eq_three_G.ediam ≤ 3 :=    SimpleGraph.ediam_le_iff.mpr cycle_seven_diam_eq_three_edist_le_three  have h_prop : (0 : Fin 7) ≠ 3 ∧ ¬ cycle_seven_diam_eq_three_G.Adj 0 3 ∧      ∀ x, x ∉ cycle_seven_diam_eq_three_G.commonNeighbors 0 3 := by    dsimp [cycle_seven_diam_eq_three_G]    decide  have h_empty : cycle_seven_diam_eq_three_G.commonNeighbors 0 3 = ∅ := by    rw [Set.eq_empty_iff_forall_notMem]    exact h_prop.2.2  have h_lt : 2 < cycle_seven_diam_eq_three_G.edist 0 3 := by    rw [SimpleGraph.two_lt_edist_iff]    exact ⟨h_prop.1, h_prop.2.1, h_empty⟩  have h_ge_edist : 3 ≤ cycle_seven_diam_eq_three_G.edist 0 3 := by    have h : (2 : ℕ) + 1 ≤ cycle_seven_diam_eq_three_G.edist 0 3 ↔ (2 : ℕ) < cycle_seven_diam_eq_three_G.edist 0 3 :=      ENat.natCast_add_one_le_iff    exact h.mpr h_lt  have h_ge : 3 ≤ cycle_seven_diam_eq_three_G.ediam :=    le_trans h_ge_edist SimpleGraph.edist_le_ediam  have h_ediam : cycle_seven_diam_eq_three_G.ediam = 3 := le_antisymm h_le h_ge  rw [SimpleGraph.diam, h_ediam]  rfl
See it in the graphDiscuss this resultChallenge it