AFTD Auto-Formalizing Theoretical Domains

srg_is_amply_regular

theoremverified

Every strongly regular graph with parameters (n, k, ℓ, μ) on a finite vertex set is an amply regular graph with parameters (k, ℓ, μ).

Statement

theorem srg_is_amply_regular {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]
    {n k ℓ μ : ℕ} (hG : G.IsSRGWith n k ℓ μ) :
    IsAmplyRegular G k ℓ μ
Source
folklore; Brouwer, Cohen, Neumaier, Distance-Regular Graphs (1989)
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…

Read back from the Lean

For any finite type $V$, any simple graph $G$ on $V$ with decidable adjacency, and any natural numbers $n$, $k$, $\ell$, and $\mu$, if $G$ is a strongly regular graph with parameters $(n, k, \ell, \mu)$ (G.IsSRGWith n k ℓ μ), then $G$ is amply regular with parameters $(k, \ell, \mu)$ (IsAmplyRegular G k ℓ μ).

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

An amply regular graph requires regularity of degree $k$, that adjacent vertices share $\ell$ common neighbors, and that vertices at distance 2 share $\mu$ common neighbors. The first two conditions hold immediately by the definition of a strongly regular graph. For the third, any two vertices at distance 2 must be distinct (since self-distance is 0) and non-adjacent (since adjacent vertices are at distance 1); hence the strong regularity property for distinct non-adjacent pairs yields that they share $\mu$ common neighbors.

  1. To show $G$ is amply regular, it suffices to prove that any two vertices at distance 2 share $\mu$ common neighbors.

    An amply regular graph requires three properties: $k$-regularity, $\ell$ common neighbors for adjacent vertices, and $\mu$ common neighbors for vertices at distance 2. The first two conditions are satisfied immediately by the strong regularity of $G$ (via `hG.regular` and `hG.of_adj`), leaving only the third property to be established for arbitrary vertices $u, v$ with $\operatorname{dist}(u, v) = 2$.

    line 5

      refine ⟨hG.regular, fun {u v} hadj => hG.of_adj u v hadj, fun {u v} hdist => ?_⟩
  2. The vertices $u$ and $v$ are distinct ($u \neq v$).

    Suppose for contradiction that $u = v$. Then the distance from $u$ to itself is 0, which contradicts the assumption that $\operatorname{dist}(u, v) = 2$.

    lines 6–8

      have hne : u ≠ v := by
        intro rfl
        simp at hdist
  3. The vertices $u$ and $v$ are not adjacent.

    Suppose for contradiction that $u$ and $v$ are adjacent. By `SimpleGraph.dist_eq_one_iff_adj`, their distance must be 1. But their distance is assumed to be 2, and linear arithmetic (`omega`) finds the contradiction $1 = 2$.

    lines 9–12

    uses SimpleGraph.dist_eq_one_iff_adj

      have hnadj : ¬ G.Adj u v := by
        intro hadj
        rw [← SimpleGraph.dist_eq_one_iff_adj] at hadj
        omega
  4. The vertices $u$ and $v$ have $\mu$ common neighbors.

    Because $u$ and $v$ are distinct and not adjacent, the definition of a strongly regular graph (`hG.of_not_adj`) ensures that they have exactly $\mu$ common neighbors, completing the proof.

    line 13

      exact hG.of_not_adj hne hnadj
SimpleGraph.dist_eq_one_iff_adj
Two vertices in a graph are adjacent if and only if the distance between them is 1.

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

/-- Every strongly regular graph with parameters (n, k, ℓ, μ) is an amply regular graph with parameters (k, ℓ, μ). -/theorem srg_is_amply_regular {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]    {n k ℓ μ : ℕ} (hG : G.IsSRGWith n k ℓ μ) :    IsAmplyRegular G k ℓ μ := by  refine ⟨hG.regular, fun {u v} hadj => hG.of_adj u v hadj, fun {u v} hdist => ?_⟩  have hne : u ≠ v := by    intro rfl    simp at hdist  have hnadj : ¬ G.Adj u v := by    intro hadj    rw [← SimpleGraph.dist_eq_one_iff_adj] at hadj    omega  exact hG.of_not_adj hne hnadj
See it in the graphDiscuss this resultChallenge it