AFTD Auto-Formalizing Theoretical Domains

amply_regular_sphere_two_card_mul

theoremverified

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.

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

    lines 5–34

    uses SimpleGraph.dist_self

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

    lines 35–70

    uses Finset.sum_congr, Finset.sum_add_distrib, Finset.sum_filter, mem_commonNeighbors, Set.toFinset_card, Finset.card_eq_sum_ones, card_neighborFinset_eq_degree

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

    lines 72–99

    uses Finset.sum_const_zero, Finset.mul_sum, Finset.sum_congr, Finset.sum_filter, Finset.card_eq_sum_ones, card_neighborFinset_eq_degree, mul_comm

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

    lines 101–130

    uses Finset.sum_filter, SimpleGraph.mem_commonNeighbors, SimpleGraph.adj_comm, Set.toFinset_card, Finset.sum_const_zero, Finset.mul_sum, Finset.sum_congr, 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]
  5. 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.

    line 132

    uses Finset.sum_comm

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

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

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