amply_regular_diameter_bound_of_diam_le_two
An amply regular graph with parameters (k, ℓ, μ) whose diameter is at most 2 has diameter at most 2k/(ℓ+2). No hypothesis on μ is needed: for diameter 1 one has ℓ < k, and for diameter 2 one has ℓ + 2 ≤ k.
Statement
theorem amply_regular_diameter_bound_of_diam_le_two {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (h2 : G.diam ≤ 2) : G.diam ≤ 2 * k / (ℓ + 2)
- Source
- step towards amply_regular_diameter_bound_conjecture
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_card_commonNeighbors_add_two_le_degreeLet G be a graph on a finite vertex set that is regular of degree k. If u and v are two distinct common neighbours of a vertex w and u is…
- IsAmplyRegularA graph G on a finite vertex set is amply regular with parameters (k, ℓ, μ) if it is regular of degree k, every pair of adjacent vertices…
The proof, explained
The bound is proved by case analysis on the diameter of G, which is assumed to be at most 2. If the diameter is 0, the inequality is trivial. If the diameter is 1, any two vertices realising the diameter are adjacent, which implies their common neighbor count ℓ is strictly less than their degree k, giving ℓ + 2 ≤ 2k. If the diameter is 2, vertices at distance 2 share a common neighbor, and regularity forces ℓ + 2 ≤ k, from which 2(ℓ + 2) ≤ 2k follows.
The diameter bound holds when the diameter of G is 0.
We split into cases based on whether diam(G) < 1. When diam(G) < 1, the diameter must be 0, and the inequality 0 ≤ 2k / (ℓ + 2) holds trivially since 0 is less than or equal to any natural number.
uses
Nat.lt_or_ge,Nat.zero_leclassical rcases Nat.lt_or_ge G.diam 1 with h1 | h1 · have hd0 : G.diam = 0 := by omega rw [hd0]; exact Nat.zero_le _
If diam(G) = 1, there exist adjacent vertices u and v realising the diameter.
We split on whether diam(G) < 2. Given diam(G) ≥ 1, this forces diam(G) = 1. Since the diameter is non-zero, the vertex set is non-empty, so there exist vertices u and v whose distance equals the diameter (1). Ruling out infinite extended distance shows edist(u, v) = 1, which means u and v are adjacent.
uses
Nat.lt_or_ge,SimpleGraph.nontrivial_of_diam_ne_zero,SimpleGraph.dist,ENat.toNat_top,ENat.natCast_toNat,SimpleGraph.edist_eq_one_iff_adj.mprcases Nat.lt_or_ge G.diam 2 with h2' | h2'' · have hd1 : G.diam = 1 := by omega have : Nonempty V := (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd1]; norm_num)).to_nonempty obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam have hnt : G.edist u v ≠ ⊤ := by intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega have h1' : (G.edist u v).toNat = 1 := huv.trans hd1 have hed : G.edist u v = 1 := by rw [← ENat.natCast_toNat hnt, h1']; rfl have hadj : G.Adj u v := SimpleGraph.edist_eq_one_iff_adj.mp hed
In an amply regular graph with diameter 1, ℓ < k.
For the adjacent vertices u and v, the number of common neighbors is strictly less than the degree of u (since v is a neighbor of u but not a common neighbor of u and v). By ample regularity, adjacent vertices have ℓ common neighbors and every vertex has degree k, which gives ℓ < k.
uses
SimpleGraph.Adj.card_commonNeighbors_lt_degreehave hlt : ℓ < k := by have hh := SimpleGraph.Adj.card_commonNeighbors_lt_degree hadj rw [hG.adj_commonNeighbors hadj, hG.regular u] at hh; exact hh
The diameter bound holds when diam(G) = 1.
When diam(G) = 1, the division inequality 1 ≤ 2k / (ℓ + 2) is equivalent to 1 * (ℓ + 2) ≤ 2k. Since ℓ < k and k ≥ 1, we have ℓ + 2 ≤ k + 1 ≤ 2k, which linear integer arithmetic confirms.
uses
Nat.le_div_iff_mul_lerw [hd1, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)] omega
If diam(G) = 2, there exist non-adjacent vertices u and v with a mutual neighbor w.
In the remaining case diam(G) ≥ 2, combining with the hypothesis diam(G) ≤ 2 yields diam(G) = 2. Since the diameter is non-zero, the graph is non-empty, so there exist vertices u and v at distance 2. Their extended distance is 2, which implies that u and v are distinct, non-adjacent, and share a common neighbor w adjacent to both.
uses
SimpleGraph.nontrivial_of_diam_ne_zero,SimpleGraph.dist,ENat.toNat_top,ENat.natCast_toNat,SimpleGraph.edist_eq_two_iff.mp,SimpleGraph.mem_commonNeighbors· have hd2 : G.diam = 2 := by omega have : Nonempty V := (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd2]; norm_num)).to_nonempty obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam have hnt : G.edist u v ≠ ⊤ := by intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega have h1' : (G.edist u v).toNat = 2 := huv.trans hd2 have hed : G.edist u v = 2 := by rw [← ENat.natCast_toNat hnt, h1']; rfl obtain ⟨hne', hnadj, hcommon⟩ := SimpleGraph.edist_eq_two_iff.mp hed obtain ⟨w, hw⟩ := hcommon rw [SimpleGraph.mem_commonNeighbors] at hw
The parameters satisfy ℓ + 2 ≤ k.
Applying the lemma simple_graph_card_commonNeighbors_add_two_le_degree to the vertices u, v, w (where u ≠ v, u ~ w, v ~ w, and u ≁ v), the number of common neighbors of u and w plus 2 is at most the degree k. Since u and w are adjacent, they have exactly ℓ common neighbors by ample regularity, giving ℓ + 2 ≤ k.
uses
simple_graph_card_commonNeighbors_add_two_le_degreehave hcount : Fintype.card (G.commonNeighbors u w) + 2 ≤ k := simple_graph_card_commonNeighbors_add_two_le_degree G hG.regular hne' hw.1 hw.2 hnadj have hEll : Fintype.card (G.commonNeighbors u w) = ℓ := hG.adj_commonNeighbors hw.1
The diameter bound holds when diam(G) = 2.
When diam(G) = 2, the inequality 2 ≤ 2k / (ℓ + 2) is equivalent to 2 * (ℓ + 2) ≤ 2k by Nat.le_div_iff_mul_le. This follows immediately by multiplying ℓ + 2 ≤ k by 2.
uses
Nat.le_div_iff_mul_lerw [hd2, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)] omega
Nat.lt_or_ge- For any two natural numbers n and m, either n < m or n ≥ m.
Nat.zero_le- Zero is less than or equal to any natural number.
SimpleGraph.nontrivial_of_diam_ne_zero- A graph with non-zero diameter has at least two vertices (it is non-trivial).
SimpleGraph.dist- The distance between two vertices in a graph, valued in ℕ (defined as the natural-number projection of the extended distance).
ENat.toNat_top- The natural-number projection of ∞ (represented by ⊤ in ℕ∞) is 0.
ENat.natCast_toNat- A finite extended natural number equals its coercion from its natural-number projection.
SimpleGraph.edist_eq_one_iff_adj.mp- If the extended distance between two vertices is 1, then they are adjacent.
SimpleGraph.Adj.card_commonNeighbors_lt_degree- The number of common neighbors of two adjacent vertices is strictly less than the degree of either vertex.
Nat.le_div_iff_mul_le- For k > 0, x ≤ y / k in natural number division if and only if x * k ≤ y.
SimpleGraph.edist_eq_two_iff.mp- If the extended distance between two vertices is 2, then they are distinct, non-adjacent, and have at least one common neighbor.
SimpleGraph.mem_commonNeighbors- A vertex belongs to the common neighbors of two vertices if and only if it is adjacent to both.
simple_graph_card_commonNeighbors_add_two_le_degree- In a k-regular graph, if distinct vertices u and v are non-adjacent and share a common neighbor w, then the number of common neighbors of u and w plus 2 is at most k.
- In Mathlib, graph distance `dist` is ℕ-valued, defined as the projection `(edist u v).toNat` of the extended distance in ℕ∞. By convention, `(⊤ : ℕ∞).toNat = 0`. Consequently, to infer that two vertices at distance 1 or 2 have extended distance 1 or 2, the proof explicitly rules out `edist u v = ⊤`, a formal detail with no counterpart in textbook mathematics.
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.
/-- Easy half of Conjecture 3.7: if the diameter is at most 2 the bound holds for every amply regular graph, with no hypothesis on μ (so in particular for μ > 2). -/theorem amply_regular_diameter_bound_of_diam_le_two {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (h2 : G.diam ≤ 2) : G.diam ≤ 2 * k / (ℓ + 2) := by classical rcases Nat.lt_or_ge G.diam 1 with h1 | h1 · have hd0 : G.diam = 0 := by omega rw [hd0]; exact Nat.zero_le _ rcases Nat.lt_or_ge G.diam 2 with h2' | h2'' · have hd1 : G.diam = 1 := by omega have : Nonempty V := (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd1]; norm_num)).to_nonempty obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam have hnt : G.edist u v ≠ ⊤ := by intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega have h1' : (G.edist u v).toNat = 1 := huv.trans hd1 have hed : G.edist u v = 1 := by rw [← ENat.natCast_toNat hnt, h1']; rfl have hadj : G.Adj u v := SimpleGraph.edist_eq_one_iff_adj.mp hed have hlt : ℓ < k := by have hh := SimpleGraph.Adj.card_commonNeighbors_lt_degree hadj rw [hG.adj_commonNeighbors hadj, hG.regular u] at hh; exact hh rw [hd1, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)] omega · have hd2 : G.diam = 2 := by omega have : Nonempty V := (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd2]; norm_num)).to_nonempty obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam have hnt : G.edist u v ≠ ⊤ := by intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega have h1' : (G.edist u v).toNat = 2 := huv.trans hd2 have hed : G.edist u v = 2 := by rw [← ENat.natCast_toNat hnt, h1']; rfl obtain ⟨hne', hnadj, hcommon⟩ := SimpleGraph.edist_eq_two_iff.mp hed obtain ⟨w, hw⟩ := hcommon rw [SimpleGraph.mem_commonNeighbors] at hw have hcount : Fintype.card (G.commonNeighbors u w) + 2 ≤ k := simple_graph_card_commonNeighbors_add_two_le_degree G hG.regular hne' hw.1 hw.2 hnadj have hEll : Fintype.card (G.commonNeighbors u w) = ℓ := hG.adj_commonNeighbors hw.1 rw [hd2, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)] omega