AFTD Auto-Formalizing Theoretical Domains

amply_regular_diameter_bound_of_diam_le_two

theoremverified

An amply regular graph with parameters (k, ℓ, μ) whose diameter is at most 2 has diameter at most 2k/(ℓ+2). No hypothesis on μ is needed: for diameter 1 one has ℓ < k, and for diameter 2 one has ℓ + 2 ≤ k.

Statement

theorem amply_regular_diameter_bound_of_diam_le_two {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]
    {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (h2 : G.diam ≤ 2) :
    G.diam ≤ 2 * k / (ℓ + 2)
Source
step towards amply_regular_diameter_bound_conjecture
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_card_commonNeighbors_add_two_le_degreeLet G be a graph on a finite vertex set that is regular of degree k. If u and v are two distinct common neighbours of a vertex w and u is…
  • 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 bound is proved by case analysis on the diameter of G, which is assumed to be at most 2. If the diameter is 0, the inequality is trivial. If the diameter is 1, any two vertices realising the diameter are adjacent, which implies their common neighbor count ℓ is strictly less than their degree k, giving ℓ + 2 ≤ 2k. If the diameter is 2, vertices at distance 2 share a common neighbor, and regularity forces ℓ + 2 ≤ k, from which 2(ℓ + 2) ≤ 2k follows.

  1. The diameter bound holds when the diameter of G is 0.

    We split into cases based on whether diam(G) < 1. When diam(G) < 1, the diameter must be 0, and the inequality 0 ≤ 2k / (ℓ + 2) holds trivially since 0 is less than or equal to any natural number.

    lines 5–8

    uses Nat.lt_or_ge, Nat.zero_le

      classical
      rcases Nat.lt_or_ge G.diam 1 with h1 | h1
      · have hd0 : G.diam = 0 := by omega
        rw [hd0]; exact Nat.zero_le _
  2. If diam(G) = 1, there exist adjacent vertices u and v realising the diameter.

    We split on whether diam(G) < 2. Given diam(G) ≥ 1, this forces diam(G) = 1. Since the diameter is non-zero, the vertex set is non-empty, so there exist vertices u and v whose distance equals the diameter (1). Ruling out infinite extended distance shows edist(u, v) = 1, which means u and v are adjacent.

    lines 9–18

    uses Nat.lt_or_ge, SimpleGraph.nontrivial_of_diam_ne_zero, SimpleGraph.dist, ENat.toNat_top, ENat.natCast_toNat, SimpleGraph.edist_eq_one_iff_adj.mp

      rcases Nat.lt_or_ge G.diam 2 with h2' | h2''
      · have hd1 : G.diam = 1 := by omega
        have : Nonempty V :=
          (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd1]; norm_num)).to_nonempty
        obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam
        have hnt : G.edist u v ≠ ⊤ := by
          intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega
        have h1' : (G.edist u v).toNat = 1 := huv.trans hd1
        have hed : G.edist u v = 1 := by rw [← ENat.natCast_toNat hnt, h1']; rfl
        have hadj : G.Adj u v := SimpleGraph.edist_eq_one_iff_adj.mp hed
  3. In an amply regular graph with diameter 1, ℓ < k.

    For the adjacent vertices u and v, the number of common neighbors is strictly less than the degree of u (since v is a neighbor of u but not a common neighbor of u and v). By ample regularity, adjacent vertices have ℓ common neighbors and every vertex has degree k, which gives ℓ < k.

    lines 19–21

    uses SimpleGraph.Adj.card_commonNeighbors_lt_degree

        have hlt : ℓ < k := by
          have hh := SimpleGraph.Adj.card_commonNeighbors_lt_degree hadj
          rw [hG.adj_commonNeighbors hadj, hG.regular u] at hh; exact hh
  4. The diameter bound holds when diam(G) = 1.

    When diam(G) = 1, the division inequality 1 ≤ 2k / (ℓ + 2) is equivalent to 1 * (ℓ + 2) ≤ 2k. Since ℓ < k and k ≥ 1, we have ℓ + 2 ≤ k + 1 ≤ 2k, which linear integer arithmetic confirms.

    lines 22–23

    uses Nat.le_div_iff_mul_le

        rw [hd1, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)]
        omega
  5. If diam(G) = 2, there exist non-adjacent vertices u and v with a mutual neighbor w.

    In the remaining case diam(G) ≥ 2, combining with the hypothesis diam(G) ≤ 2 yields diam(G) = 2. Since the diameter is non-zero, the graph is non-empty, so there exist vertices u and v at distance 2. Their extended distance is 2, which implies that u and v are distinct, non-adjacent, and share a common neighbor w adjacent to both.

    lines 24–34

    uses SimpleGraph.nontrivial_of_diam_ne_zero, SimpleGraph.dist, ENat.toNat_top, ENat.natCast_toNat, SimpleGraph.edist_eq_two_iff.mp, SimpleGraph.mem_commonNeighbors

      · have hd2 : G.diam = 2 := by omega
        have : Nonempty V :=
          (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd2]; norm_num)).to_nonempty
        obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam
        have hnt : G.edist u v ≠ ⊤ := by
          intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega
        have h1' : (G.edist u v).toNat = 2 := huv.trans hd2
        have hed : G.edist u v = 2 := by rw [← ENat.natCast_toNat hnt, h1']; rfl
        obtain ⟨hne', hnadj, hcommon⟩ := SimpleGraph.edist_eq_two_iff.mp hed
        obtain ⟨w, hw⟩ := hcommon
        rw [SimpleGraph.mem_commonNeighbors] at hw
  6. The parameters satisfy ℓ + 2 ≤ k.

    Applying the lemma simple_graph_card_commonNeighbors_add_two_le_degree to the vertices u, v, w (where u ≠ v, u ~ w, v ~ w, and u ≁ v), the number of common neighbors of u and w plus 2 is at most the degree k. Since u and w are adjacent, they have exactly ℓ common neighbors by ample regularity, giving ℓ + 2 ≤ k.

    lines 35–37

    uses simple_graph_card_commonNeighbors_add_two_le_degree

        have hcount : Fintype.card (G.commonNeighbors u w) + 2 ≤ k :=
          simple_graph_card_commonNeighbors_add_two_le_degree G hG.regular hne' hw.1 hw.2 hnadj
        have hEll : Fintype.card (G.commonNeighbors u w) = ℓ := hG.adj_commonNeighbors hw.1
  7. The diameter bound holds when diam(G) = 2.

    When diam(G) = 2, the inequality 2 ≤ 2k / (ℓ + 2) is equivalent to 2 * (ℓ + 2) ≤ 2k by Nat.le_div_iff_mul_le. This follows immediately by multiplying ℓ + 2 ≤ k by 2.

    lines 38–39

    uses Nat.le_div_iff_mul_le

        rw [hd2, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)]
        omega
Nat.lt_or_ge
For any two natural numbers n and m, either n < m or n ≥ m.
Nat.zero_le
Zero is less than or equal to any natural number.
SimpleGraph.nontrivial_of_diam_ne_zero
A graph with non-zero diameter has at least two vertices (it is non-trivial).
SimpleGraph.dist
The distance between two vertices in a graph, valued in ℕ (defined as the natural-number projection of the extended distance).
ENat.toNat_top
The natural-number projection of ∞ (represented by ⊤ in ℕ∞) is 0.
ENat.natCast_toNat
A finite extended natural number equals its coercion from its natural-number projection.
SimpleGraph.edist_eq_one_iff_adj.mp
If the extended distance between two vertices is 1, then they are adjacent.
SimpleGraph.Adj.card_commonNeighbors_lt_degree
The number of common neighbors of two adjacent vertices is strictly less than the degree of either vertex.
Nat.le_div_iff_mul_le
For k > 0, x ≤ y / k in natural number division if and only if x * k ≤ y.
SimpleGraph.edist_eq_two_iff.mp
If the extended distance between two vertices is 2, then they are distinct, non-adjacent, and have at least one common neighbor.
SimpleGraph.mem_commonNeighbors
A vertex belongs to the common neighbors of two vertices if and only if it is adjacent to both.
simple_graph_card_commonNeighbors_add_two_le_degree
In a k-regular graph, if distinct vertices u and v are non-adjacent and share a common neighbor w, then the number of common neighbors of u and w plus 2 is at most k.

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

/-- Easy half of Conjecture 3.7: if the diameter is at most 2 the bound holds for every amply regular graph, with no hypothesis on μ (so in particular for μ > 2). -/theorem amply_regular_diameter_bound_of_diam_le_two {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]    {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (h2 : G.diam ≤ 2) :    G.diam ≤ 2 * k / (ℓ + 2) := by  classical  rcases Nat.lt_or_ge G.diam 1 with h1 | h1  · have hd0 : G.diam = 0 := by omega    rw [hd0]; exact Nat.zero_le _  rcases Nat.lt_or_ge G.diam 2 with h2' | h2''  · have hd1 : G.diam = 1 := by omega    have : Nonempty V :=      (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd1]; norm_num)).to_nonempty    obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam    have hnt : G.edist u v ≠ ⊤ := by      intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega    have h1' : (G.edist u v).toNat = 1 := huv.trans hd1    have hed : G.edist u v = 1 := by rw [← ENat.natCast_toNat hnt, h1']; rfl    have hadj : G.Adj u v := SimpleGraph.edist_eq_one_iff_adj.mp hed    have hlt : ℓ < k := by      have hh := SimpleGraph.Adj.card_commonNeighbors_lt_degree hadj      rw [hG.adj_commonNeighbors hadj, hG.regular u] at hh; exact hh    rw [hd1, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)]    omega  · have hd2 : G.diam = 2 := by omega    have : Nonempty V :=      (SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hd2]; norm_num)).to_nonempty    obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam    have hnt : G.edist u v ≠ ⊤ := by      intro htop; rw [SimpleGraph.dist, htop, ENat.toNat_top] at huv; omega    have h1' : (G.edist u v).toNat = 2 := huv.trans hd2    have hed : G.edist u v = 2 := by rw [← ENat.natCast_toNat hnt, h1']; rfl    obtain ⟨hne', hnadj, hcommon⟩ := SimpleGraph.edist_eq_two_iff.mp hed    obtain ⟨w, hw⟩ := hcommon    rw [SimpleGraph.mem_commonNeighbors] at hw    have hcount : Fintype.card (G.commonNeighbors u w) + 2 ≤ k :=      simple_graph_card_commonNeighbors_add_two_le_degree G hG.regular hne' hw.1 hw.2 hnadj    have hEll : Fintype.card (G.commonNeighbors u w) = ℓ := hG.adj_commonNeighbors hw.1    rw [hd2, Nat.le_div_iff_mul_le (k := ℓ + 2) (by omega)]    omega
See it in the graphDiscuss this resultChallenge it