AFTD Auto-Formalizing Theoretical Domains

amply_regular_mu_le_degree_of_dist_two

theoremverified

In an amply regular graph with parameters (k, ℓ, μ), if there exists a pair of vertices at distance 2, then μ ≤ k.

Statement

theorem amply_regular_mu_le_degree_of_dist_two {V : Type*} [Fintype V] {G : SimpleGraph V}
    [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ)
    {u v : V} (huv : G.dist u v = 2) : μ ≤ k
Source
step towards simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_bound
Verified
01 Nov 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

In an amply regular graph, any two vertices at distance 2 share exactly μ common neighbors by definition. Since every common neighbor of u and v is in particular a neighbor of u, the set of common neighbors embeds into the neighborhood of u. The cardinality μ is therefore bounded by the degree of u, which equals k by graph regularity.

  1. The common neighbors of u and v form a subset of the neighbors of u (G.commonNeighbors u v ⊆ G.neighborSet u).

    Let w be an arbitrary common neighbor of u and v. By SimpleGraph.mem_commonNeighbors, w is adjacent to both u and v. In particular, w is adjacent to u, so w belongs to the neighbor set of u.

    lines 5–8

    uses SimpleGraph.mem_commonNeighbors

      have hsub : G.commonNeighbors u v ⊆ G.neighborSet u := by
        intro w hw
        rw [SimpleGraph.mem_commonNeighbors] at hw
        exact hw.1
  2. The number of common neighbors of u and v is at most the number of neighbors of u (|G.commonNeighbors u v| ≤ |G.neighborSet u|).

    Using the subset relation from the previous step, we construct an inclusion map sending each common neighbor w to itself as an element of the neighbor set of u. To show this map is injective, we take two elements with the same image and apply extensionality and congrArg (projecting to the underlying vertex) to conclude they are equal. By Fintype.card_le_of_injective, the existence of this injection establishes the inequality on cardinalities.

    lines 9–13

    uses Fintype.card_le_of_injective, congrArg

      have hcard : Fintype.card (G.commonNeighbors u v) ≤ Fintype.card (G.neighborSet u) := by
        refine Fintype.card_le_of_injective (fun w : G.commonNeighbors u v => (⟨w.1, hsub w.2⟩ : G.neighborSet u)) ?_
        intro a b h
        ext
        exact congrArg (fun x : G.neighborSet u => (x : V)) h
  3. μ ≤ k

    Since u and v are at distance 2, the definition of an amply regular graph states that they have exactly μ common neighbors, allowing us to rewrite μ as |G.commonNeighbors u v|. A calculation then chains the relations: |G.commonNeighbors u v| ≤ |G.neighborSet u| by the previous inequality, |G.neighborSet u| = G.degree u by SimpleGraph.card_neighborSet_eq_degree, and G.degree u = k because an amply regular graph is regular of degree k.

    lines 14–18

    uses SimpleGraph.card_neighborSet_eq_degree

      rw [← hG.dist_two_commonNeighbors huv]
      calc
        Fintype.card (G.commonNeighbors u v) ≤ Fintype.card (G.neighborSet u) := hcard
        _ = G.degree u := SimpleGraph.card_neighborSet_eq_degree G u
        _ = k := hG.regular.degree_eq u
SimpleGraph.mem_commonNeighbors
A vertex belongs to the set of common neighbors of two vertices if and only if it is adjacent to both.
Fintype.card_le_of_injective
If an injective function exists between two finite types, the cardinality of the domain is at most the cardinality of the codomain.
congrArg
A function applied to equal inputs produces equal outputs: if a = b, then f(a) = f(b).
SimpleGraph.card_neighborSet_eq_degree
The cardinality of the neighbor set of a vertex equals the degree of that vertex.

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

/-- In an amply regular graph with parameters (k, ℓ, μ), if there exists a pair of vertices at distance 2, then μ ≤ k. -/theorem amply_regular_mu_le_degree_of_dist_two {V : Type*} [Fintype V] {G : SimpleGraph V}    [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ)    {u v : V} (huv : G.dist u v = 2) : μ ≤ k := by  have hsub : G.commonNeighbors u v ⊆ G.neighborSet u := by    intro w hw    rw [SimpleGraph.mem_commonNeighbors] at hw    exact hw.1  have hcard : Fintype.card (G.commonNeighbors u v) ≤ Fintype.card (G.neighborSet u) := by    refine Fintype.card_le_of_injective (fun w : G.commonNeighbors u v => (⟨w.1, hsub w.2⟩ : G.neighborSet u)) ?_    intro a b h    ext    exact congrArg (fun x : G.neighborSet u => (x : V)) h  rw [← hG.dist_two_commonNeighbors huv]  calc    Fintype.card (G.commonNeighbors u v) ≤ Fintype.card (G.neighborSet u) := hcard    _ = G.degree u := SimpleGraph.card_neighborSet_eq_degree G u    _ = k := hG.regular.degree_eq u
See it in the graphDiscuss this resultChallenge it