cycle_seven_diam_eq_three
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
- exists_planar_all_powers_well_covered_diam_eq_threeThere exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive…
- exists_triangle_free_all_powers_well_covered_diam_eq_threeThere exists a finite connected triangle-free simple graph G with at least two vertices whose diameter is exactly 3 and such that every…
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.
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.
uses
Or.inr,Or.inlprivate 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)
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.
uses
SimpleGraph.edist_eq_one_iff_adj.mprprivate 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)]
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.
uses
SimpleGraph.edist_triangle,add_assoc,le_trans,add_le_addprivate 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)
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.
uses
SimpleGraph.edist_triangle,sub_sub,le_trans,add_le_addprivate 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)
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.
uses
Fin.add_def,Fin.sub_def,le_transprivate 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)
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.
uses
le_transprivate 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 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.
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
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).
uses
Set.eq_empty_iff_forall_notMem,SimpleGraph.two_lt_edist_iffhave 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⟩
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.
uses
ENat.natCast_add_one_le_iff,le_trans,SimpleGraph.edist_le_ediam,le_antisymm,SimpleGraph.diamhave 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).
- In Lean's SimpleGraph library, the graph diameter diam is defined as a natural number by converting the extended natural diameter ediam via ENat.toNat. Consequently, the proof establishes upper and lower bounds on ediam first before concluding for diam.
- The lower bound relies on finite exhaustion (decide) to check that vertices 0 and 3 in Fin 7 share no common neighbors, and modular arithmetic identities in Fin 7 are automated using omega.
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.
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