amply_regular_sphere_two_card_mul
In an amply regular graph with parameters (k, ℓ, μ), for every vertex v the number of vertices at distance exactly 2 from v, multiplied by μ, equals k(k − 1 − ℓ).
Statement
theorem amply_regular_sphere_two_card_mul {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (v : V) : (Finset.univ.filter (fun w => G.dist v w = 2)).card * μ = k * (k - 1 - ℓ)
- Source
- step towards amply_regular_diameter_bound_conjecture
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 identity |S₂(v)| · μ = k(k - 1 - ℓ) is proved by double counting the set of pairs (w, z) such that w is a neighbor of v, z is a neighbor of w, and the distance between v and z is 2. Summing over w first, the neighbors of each of the k neighbors of v partition into v itself (1 vertex), the common neighbors of v and w (ℓ vertices), and the distance-2 vertices, giving k - 1 - ℓ choices of z for each w, for a total of k(k - 1 - ℓ). Summing over z first, each of the |S₂(v)| vertices at distance 2 from v has exactly μ common neighbors with v, giving |S₂(v)| · μ in total. Equating the two counts by interchanging the summation order yields the result.
For any neighbor w of v and any vertex z, the indicator of adjacency between w and z decomposes into the sum of three indicators: z = v, v is adjacent to z, and the distance between v and z is 2.
Given that w is adjacent to v, any neighbor z of w is either equal to v, adjacent to v, or at distance 2 from v. If z = v, it cannot be adjacent to v (as the graph has no self-loops) and its distance to v is 0 ≠ 2. If z ≠ v and v is adjacent to z, the distance is 1 ≠ 2. If z ≠ v and v is not adjacent to z, the two-edge walk v ~ w ~ z gives an upper bound dist(v, z) ≤ 2; since the distance cannot be 0 or 1, it must be exactly 2. Exactly one of the three indicators is 1, and the other two are 0.
uses
SimpleGraph.dist_selfclassical open SimpleGraph in have sum_z_d_add (w : V) (hvw : G.Adj v w) : (∑ z : V, if G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0) + 1 + ℓ = k := by have hid (z : V) : (if G.Adj w z ∧ G.dist v z = 2 then 1 else 0) + (if G.Adj w z ∧ z = v then 1 else 0) + (if G.Adj w z ∧ G.Adj v z then 1 else 0) = (if G.Adj w z then (1 : ℕ) else 0) := by by_cases hwz : G.Adj w z · simp only [hwz, true_and, ite_true] by_cases hzv : z = v · have hnotadj : ¬ G.Adj v z := by rw [hzv]; exact G.irrefl have hdist : G.dist v z ≠ 2 := by rw [hzv, SimpleGraph.dist_self]; decide simp only [if_pos hzv, if_neg hnotadj, if_neg hdist, add_zero, zero_add] · simp only [if_neg hzv, add_zero] by_cases hvz : G.Adj v z · have hd1 : G.dist v z = 1 := dist_eq_one_iff_adj.mpr hvz have hd2 : G.dist v z ≠ 2 := by rw [hd1]; decide simp only [if_pos hvz, if_neg hd2, zero_add] · have hd2 : G.dist v z = 2 := by let p : G.Walk v z := Walk.cons hvw (Walk.cons hwz Walk.nil) have hp : p.length = 2 := by simp [p] have hle : G.dist v z ≤ 2 := hp ▸ G.dist_le p have hr : G.Reachable v z := ⟨p⟩ have hne0 : G.dist v z ≠ 0 := fun h0 => hzv (hr.dist_eq_zero_iff.mp h0).symm have hne1 : G.dist v z ≠ 1 := fun h1 => hvz (dist_eq_one_iff_adj.mp h1) omega simp only [if_neg hvz, if_pos hd2, add_zero] · simp [hwz]
For any neighbor w of v, the number of neighbors of w at distance 2 from v plus 1 + ℓ equals k.
Summing the indicator identity over all vertices z and distributing the sum gives three contributions: vertices equal to v (which sum to 1 since w is adjacent to v), vertices adjacent to both w and v (which sum to ℓ, the number of common neighbors of an adjacent pair in an amply regular graph), and vertices adjacent to w at distance 2 from v. The total sum is the degree of w, which equals k by k-regularity.
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_filter,mem_commonNeighbors,Set.toFinset_card,Finset.card_eq_sum_ones,card_neighborFinset_eq_degreehave hsum : ∑ z : V, ((if G.Adj w z ∧ G.dist v z = 2 then 1 else 0) + (if G.Adj w z ∧ z = v then 1 else 0) + (if G.Adj w z ∧ G.Adj v z then 1 else 0)) = ∑ z : V, if G.Adj w z then (1:ℕ) else 0 := Finset.sum_congr rfl (fun z _ => hid z) rw [Finset.sum_add_distrib, Finset.sum_add_distrib] at hsum have ha : (∑ z : V, if G.Adj w z ∧ z = v then 1 else 0) = 1 := by have : (∑ z : V, if G.Adj w z ∧ z = v then 1 else 0) = ∑ z : V, (if z = v then (if G.Adj w z then (1:ℕ) else 0) else 0) := by apply Finset.sum_congr rfl intro x _ by_cases hx : x = v <;> simp [hx] rw [this] simp [hvw.symm] have hc : (∑ z : V, if G.Adj w z ∧ G.Adj v z then (1:ℕ) else 0) = ℓ := by have : (∑ z : V, if G.Adj w z ∧ G.Adj v z then (1:ℕ) else 0) = (Finset.univ.filter (fun z => G.Adj w z ∧ G.Adj v z)).card := by rw [← Finset.sum_filter] simp have hcomm : (Finset.univ.filter (fun z => G.Adj w z ∧ G.Adj v z)) = (G.commonNeighbors w v).toFinset := by ext x simp [mem_commonNeighbors] rw [this, hcomm, Set.toFinset_card, hG.adj_commonNeighbors hvw.symm] have ht : (∑ z : V, if G.Adj w z then (1:ℕ) else 0) = k := by have : (∑ z : V, if G.Adj w z then (1:ℕ) else 0) = (G.neighborFinset w).card := by rw [← Finset.sum_filter] have hfilt : (Finset.univ.filter (fun z => G.Adj w z)) = G.neighborFinset w := by ext x simp [neighborFinset, mem_neighborSet] rw [hfilt] exact (Finset.card_eq_sum_ones (G.neighborFinset w)).symm rw [this, card_neighborFinset_eq_degree, hG.regular w] rw [ha, hc] at hsum rw [ht] at hsum exact hsum
Summing the indicator of v ~ w ~ z and dist(v, z) = 2 over w first, then z, equals k(k - 1 - ℓ).
For each vertex w, if w is not adjacent to v the summand is 0. If w is adjacent to v, the inner sum over z counts neighbors of w at distance 2 from v, which equals k - 1 - ℓ by the previous lemma. Factoring out k - 1 - ℓ leaves the sum over the neighbors of v, which equals the degree k of v. Multiplying gives k(k - 1 - ℓ).
uses
Finset.sum_const_zero,Finset.mul_sum,Finset.sum_congr,Finset.sum_filter,Finset.card_eq_sum_ones,card_neighborFinset_eq_degree,mul_commhave way1 : (∑ w : V, ∑ z : V, (if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0)) = k * (k - 1 - ℓ) := by have hw (w : V) : (∑ z : V, if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0) = if G.Adj v w then k - 1 - ℓ else 0 := by by_cases hvw : G.Adj v w · simp only [hvw, true_and, if_pos] have h := sum_z_d_add w hvw omega · simp only [hvw, false_and, if_neg, not_false_eq_true] exact Finset.sum_const_zero simp_rw [hw] have hmul : (∑ w : V, if G.Adj v w then k - 1 - ℓ else 0) = (k - 1 - ℓ) * (∑ w : V, if G.Adj v w then 1 else 0) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x _ by_cases h : G.Adj v x <;> simp [h] rw [hmul] have ht : (∑ w : V, if G.Adj v w then (1:ℕ) else 0) = k := by have : (∑ w : V, if G.Adj v w then (1:ℕ) else 0) = (G.neighborFinset v).card := by rw [← Finset.sum_filter] have hfilt : (Finset.univ.filter (fun w => G.Adj v w)) = G.neighborFinset v := by ext x simp [neighborFinset, mem_neighborSet] rw [hfilt] exact (Finset.card_eq_sum_ones (G.neighborFinset v)).symm rw [this, card_neighborFinset_eq_degree, hG.regular v] rw [ht, mul_comm]
Summing the indicator of v ~ w ~ z and dist(v, z) = 2 over z first, then w, equals the number of vertices at distance 2 from v multiplied by μ.
For each vertex z, if dist(v, z) ≠ 2 the inner sum is 0. If dist(v, z) = 2, the inner sum over w counts vertices w adjacent to both v and z, which is the number of common neighbors of v and z. By ample regularity, any pair of vertices at distance 2 has exactly μ common neighbors. Factoring out μ leaves the sum of 1 over all vertices at distance 2 from v, which is the size of the sphere of radius 2.
uses
Finset.sum_filter,SimpleGraph.mem_commonNeighbors,SimpleGraph.adj_comm,Set.toFinset_card,Finset.sum_const_zero,Finset.mul_sum,Finset.sum_congr,mul_commhave way2 : (∑ z : V, ∑ w : V, (if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0)) = (Finset.univ.filter (fun w => G.dist v w = 2)).card * μ := by have hz (z : V) : (∑ w : V, if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0) = if G.dist v z = 2 then μ else 0 := by by_cases hdist : G.dist v z = 2 · simp only [hdist, and_true, if_pos] have heq : (∑ w : V, if G.Adj v w ∧ G.Adj w z then (1:ℕ) else 0) = (Finset.univ.filter (fun w => G.Adj v w ∧ G.Adj w z)).card := by rw [← Finset.sum_filter] simp have hfilt : (Finset.univ.filter (fun w => G.Adj v w ∧ G.Adj w z)) = (G.commonNeighbors v z).toFinset := by ext x simp [SimpleGraph.mem_commonNeighbors, SimpleGraph.adj_comm] rw [heq, hfilt, Set.toFinset_card, hG.dist_two_commonNeighbors hdist] · simp only [hdist, and_false, if_neg, not_false_eq_true] exact Finset.sum_const_zero simp_rw [hz] have hmul : (∑ z : V, if G.dist v z = 2 then μ else 0) = μ * (∑ z : V, if G.dist v z = 2 then 1 else 0) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x _ by_cases h : G.dist v x = 2 <;> simp [h] rw [hmul] have hcard : (∑ z : V, if G.dist v z = 2 then (1:ℕ) else 0) = (Finset.univ.filter (fun w => G.dist v w = 2)).card := by rw [← Finset.sum_filter] simp rw [hcard, mul_comm]
The number of vertices at distance 2 from v multiplied by μ equals k(k - 1 - ℓ).
The two double sums are identical up to exchanging the order of summation. Equating the results of the two counting orders completes the proof.
uses
Finset.sum_commrw [← way2, Finset.sum_comm, way1]
SimpleGraph.dist_self- The distance from any vertex to itself is 0 (dist v v = 0).
Finset.sum_congr- If two finite index sets are equal and the summands agree on each element, the sums are equal.
Finset.sum_add_distrib- Summing a pointwise sum of functions over a finite set equals the sum of the two sums.
Finset.sum_filter- Summing over elements satisfying a predicate equals summing the conditional indicator over the entire finite set.
mem_commonNeighbors- A vertex u belongs to the common neighbors of v and w if and only if it is adjacent to both.
Set.toFinset_card- The cardinality of the finite set coercion of a set equals the cardinality of the subtype.
Finset.card_eq_sum_ones- The cardinality of a finite set is the sum of 1 over all of its elements.
card_neighborFinset_eq_degree- The number of neighbors in the neighborhood finset of a vertex equals its degree.
Finset.sum_const_zero- The sum of 0 over any finite set is 0.
Finset.mul_sum- Multiplication by a factor distributes across a finite sum.
mul_comm- Multiplication is commutative (a * b = b * a).
SimpleGraph.mem_commonNeighbors- A vertex u is in the common neighbors of v and w if and only if u is adjacent to both v and w.
SimpleGraph.adj_comm- Adjacency in an undirected graph is symmetric.
Finset.sum_comm- The order of summation in a finite double sum can be interchanged.
- The proof establishes the pointwise partition of the neighborhood of w by an explicit walk construction of length 2 and case analysis on distances.
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.
/-- The sphere-size identity for amply regular graphs: k(k−1−ℓ) = |S₂(v)|·μ, so the second neighbourhood has size k(k−1−ℓ)/μ. -/theorem amply_regular_sphere_two_card_mul {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (v : V) : (Finset.univ.filter (fun w => G.dist v w = 2)).card * μ = k * (k - 1 - ℓ) := by classical open SimpleGraph in have sum_z_d_add (w : V) (hvw : G.Adj v w) : (∑ z : V, if G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0) + 1 + ℓ = k := by have hid (z : V) : (if G.Adj w z ∧ G.dist v z = 2 then 1 else 0) + (if G.Adj w z ∧ z = v then 1 else 0) + (if G.Adj w z ∧ G.Adj v z then 1 else 0) = (if G.Adj w z then (1 : ℕ) else 0) := by by_cases hwz : G.Adj w z · simp only [hwz, true_and, ite_true] by_cases hzv : z = v · have hnotadj : ¬ G.Adj v z := by rw [hzv]; exact G.irrefl have hdist : G.dist v z ≠ 2 := by rw [hzv, SimpleGraph.dist_self]; decide simp only [if_pos hzv, if_neg hnotadj, if_neg hdist, add_zero, zero_add] · simp only [if_neg hzv, add_zero] by_cases hvz : G.Adj v z · have hd1 : G.dist v z = 1 := dist_eq_one_iff_adj.mpr hvz have hd2 : G.dist v z ≠ 2 := by rw [hd1]; decide simp only [if_pos hvz, if_neg hd2, zero_add] · have hd2 : G.dist v z = 2 := by let p : G.Walk v z := Walk.cons hvw (Walk.cons hwz Walk.nil) have hp : p.length = 2 := by simp [p] have hle : G.dist v z ≤ 2 := hp ▸ G.dist_le p have hr : G.Reachable v z := ⟨p⟩ have hne0 : G.dist v z ≠ 0 := fun h0 => hzv (hr.dist_eq_zero_iff.mp h0).symm have hne1 : G.dist v z ≠ 1 := fun h1 => hvz (dist_eq_one_iff_adj.mp h1) omega simp only [if_neg hvz, if_pos hd2, add_zero] · simp [hwz] have hsum : ∑ z : V, ((if G.Adj w z ∧ G.dist v z = 2 then 1 else 0) + (if G.Adj w z ∧ z = v then 1 else 0) + (if G.Adj w z ∧ G.Adj v z then 1 else 0)) = ∑ z : V, if G.Adj w z then (1:ℕ) else 0 := Finset.sum_congr rfl (fun z _ => hid z) rw [Finset.sum_add_distrib, Finset.sum_add_distrib] at hsum have ha : (∑ z : V, if G.Adj w z ∧ z = v then 1 else 0) = 1 := by have : (∑ z : V, if G.Adj w z ∧ z = v then 1 else 0) = ∑ z : V, (if z = v then (if G.Adj w z then (1:ℕ) else 0) else 0) := by apply Finset.sum_congr rfl intro x _ by_cases hx : x = v <;> simp [hx] rw [this] simp [hvw.symm] have hc : (∑ z : V, if G.Adj w z ∧ G.Adj v z then (1:ℕ) else 0) = ℓ := by have : (∑ z : V, if G.Adj w z ∧ G.Adj v z then (1:ℕ) else 0) = (Finset.univ.filter (fun z => G.Adj w z ∧ G.Adj v z)).card := by rw [← Finset.sum_filter] simp have hcomm : (Finset.univ.filter (fun z => G.Adj w z ∧ G.Adj v z)) = (G.commonNeighbors w v).toFinset := by ext x simp [mem_commonNeighbors] rw [this, hcomm, Set.toFinset_card, hG.adj_commonNeighbors hvw.symm] have ht : (∑ z : V, if G.Adj w z then (1:ℕ) else 0) = k := by have : (∑ z : V, if G.Adj w z then (1:ℕ) else 0) = (G.neighborFinset w).card := by rw [← Finset.sum_filter] have hfilt : (Finset.univ.filter (fun z => G.Adj w z)) = G.neighborFinset w := by ext x simp [neighborFinset, mem_neighborSet] rw [hfilt] exact (Finset.card_eq_sum_ones (G.neighborFinset w)).symm rw [this, card_neighborFinset_eq_degree, hG.regular w] rw [ha, hc] at hsum rw [ht] at hsum exact hsum have way1 : (∑ w : V, ∑ z : V, (if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0)) = k * (k - 1 - ℓ) := by have hw (w : V) : (∑ z : V, if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0) = if G.Adj v w then k - 1 - ℓ else 0 := by by_cases hvw : G.Adj v w · simp only [hvw, true_and, if_pos] have h := sum_z_d_add w hvw omega · simp only [hvw, false_and, if_neg, not_false_eq_true] exact Finset.sum_const_zero simp_rw [hw] have hmul : (∑ w : V, if G.Adj v w then k - 1 - ℓ else 0) = (k - 1 - ℓ) * (∑ w : V, if G.Adj v w then 1 else 0) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x _ by_cases h : G.Adj v x <;> simp [h] rw [hmul] have ht : (∑ w : V, if G.Adj v w then (1:ℕ) else 0) = k := by have : (∑ w : V, if G.Adj v w then (1:ℕ) else 0) = (G.neighborFinset v).card := by rw [← Finset.sum_filter] have hfilt : (Finset.univ.filter (fun w => G.Adj v w)) = G.neighborFinset v := by ext x simp [neighborFinset, mem_neighborSet] rw [hfilt] exact (Finset.card_eq_sum_ones (G.neighborFinset v)).symm rw [this, card_neighborFinset_eq_degree, hG.regular v] rw [ht, mul_comm] have way2 : (∑ z : V, ∑ w : V, (if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0)) = (Finset.univ.filter (fun w => G.dist v w = 2)).card * μ := by have hz (z : V) : (∑ w : V, if G.Adj v w ∧ G.Adj w z ∧ G.dist v z = 2 then (1:ℕ) else 0) = if G.dist v z = 2 then μ else 0 := by by_cases hdist : G.dist v z = 2 · simp only [hdist, and_true, if_pos] have heq : (∑ w : V, if G.Adj v w ∧ G.Adj w z then (1:ℕ) else 0) = (Finset.univ.filter (fun w => G.Adj v w ∧ G.Adj w z)).card := by rw [← Finset.sum_filter] simp have hfilt : (Finset.univ.filter (fun w => G.Adj v w ∧ G.Adj w z)) = (G.commonNeighbors v z).toFinset := by ext x simp [SimpleGraph.mem_commonNeighbors, SimpleGraph.adj_comm] rw [heq, hfilt, Set.toFinset_card, hG.dist_two_commonNeighbors hdist] · simp only [hdist, and_false, if_neg, not_false_eq_true] exact Finset.sum_const_zero simp_rw [hz] have hmul : (∑ z : V, if G.dist v z = 2 then μ else 0) = μ * (∑ z : V, if G.dist v z = 2 then 1 else 0) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x _ by_cases h : G.dist v x = 2 <;> simp [h] rw [hmul] have hcard : (∑ z : V, if G.dist v z = 2 then (1:ℕ) else 0) = (Finset.univ.filter (fun w => G.dist v w = 2)).card := by rw [← Finset.sum_filter] simp rw [hcard, mul_comm] rw [← way2, Finset.sum_comm, way1]