AFTD Auto-Formalizing Theoretical Domains

is_distance_regular_with

def

A simple graph G on vertex type V is a distance-regular graph with diameter d : ℕ and intersection parameters b, c : Fin d → ℕ if: G is connected, G.diam = d, for every i : Fin d and all vertices x, y : V, if G.dist x y = i.val then the cardinality (Nat.card) of the subtype of vertices z : V such that G.Adj y z and G.dist x z = i.val + 1 is b i, and for every i : Fin d and all vertices x, y : V, if G.dist x y = i.val + 1 then the cardinality (Nat.card) of the subtype of vertices z : V such that G.Adj y z and G.dist x z = i.val is c i.

Statement

def is_distance_regular_with {V : Type*} (G : SimpleGraph V) (d : ℕ)
    (b c : Fin d → ℕ) : Prop
Defined in
arXiv:2611.05762, Sec. 3.1
Verified
05 Nov 2026
Axioms
none listed
Used by 2
  • distance_regular_exists_dist_eq_succIn any finite distance-regular graph G with parameters d, b, c, for every index i : Fin d, there exist vertices u, v at distance i + 1.
  • is_realizable_intersection_arrayAn intersection array (b, c) with b, c : Fin d → ℕ of diameter d is realizable if there exists a finite nonempty vertex type V and a…

Read back from the Lean

Given a type V, a simple graph G on V, a natural number d : ℕ, and functions b, c : Fin d → ℕ, the predicate is_distance_regular_with G d b c asserts that all of the following hold: 1. G is connected (G.Connected). 2. The diameter of G is equal to d (G.diam = d). 3. For every i : Fin d and all vertices x, y : V, if the graph distance between x and y in G is i.val, then the cardinality (Nat.card) of the set of vertices z : V that are adjacent to y and at distance i.val + 1 from x is equal to b i. 4. For every i : Fin d and all vertices x, y : V, if the graph distance between x and y in G is i.val + 1, then the cardinality (Nat.card) of the set of vertices z : V that are adjacent to y and at distance i.val from x is equal to c i.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A simple graph is distance-regular with diameter d and intersection parameters (b, c) if it is connected, has G.diam = d, and the Nat.card of step-forward and step-backward neighbors depends only on distance. -/
def is_distance_regular_with {V : Type*} (G : SimpleGraph V) (d : ℕ)
    (b c : Fin d → ℕ) : Prop := G.Connected ∧ G.diam = d ∧
  (∀ (i : Fin d) ⦃x y : V⦄, G.dist x y = i.val →
    Nat.card {z : V // G.Adj y z ∧ G.dist x z = i.val + 1} = b i) ∧
  (∀ (i : Fin d) ⦃x y : V⦄, G.dist x y = i.val + 1 →
    Nat.card {z : V // G.Adj y z ∧ G.dist x z = i.val} = c i)
See it in the graphDiscuss this resultChallenge it