AFTD Auto-Formalizing Theoretical Domains

amply_regular_lambda_add_two_le_degree_of_three_le_diam

theoremverified

An amply regular graph with parameters (k, ℓ, μ) whose diameter is at least 3 satisfies ℓ + 2 ≤ k. (Equivalently: if k ≤ ℓ + 1 then the diameter is at most 2.)

Statement

theorem amply_regular_lambda_add_two_le_degree_of_three_le_diam {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]
    {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (h3 : 3 ≤ G.diam) :
    ℓ + 2 ≤ k
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

Since the diameter of $G$ is at least 3, we can choose two vertices $x$ and $y$ at distance $\operatorname{dist}(x, y) = \operatorname{diam}(G) \ge 3$ connected by a shortest path $p$. Letting $p(1)$ and $p(2)$ denote the first two vertices after $x$ along $p$, the minimality of $p$ ensures that $x$ and $p(2)$ are distinct and non-adjacent, while both are adjacent to $p(1)$. Because $G$ is amply regular and $x \sim p(1)$, their common neighborhood contains exactly $\ell$ vertices, none of which can be $x$ or $p(2)$. Accounting for these $\ell$ common neighbors together with the two distinct neighbors $x$ and $p(2)$ inside the $k$-element neighborhood of $p(1)$ yields $\ell + 2 \le k$.

  1. There exist vertices $x, y \in V$ whose distance equals the diameter of $G$, which is at least 3.

    Since the diameter of $G$ is at least 3, it is non-zero, so the vertex set $V$ has at least two elements and is therefore nonempty. In a nonempty graph, the diameter is realized as the distance between some pair of vertices $x, y$, giving $\operatorname{dist}(x, y) = \operatorname{diam}(G) \ge 3$.

    lines 5–9

    uses SimpleGraph.nontrivial_of_diam_ne_zero, SimpleGraph.exists_dist_eq_diam

      classical
      have hpos : G.diam ≠ 0 := by omega
      have : Nonempty V := (SimpleGraph.nontrivial_of_diam_ne_zero hpos).to_nonempty
      obtain ⟨x, y, hxy⟩ := SimpleGraph.exists_dist_eq_diam (G := G)
      have hd : 3 ≤ G.dist x y := by omega
  2. $x$ and $y$ are connected by a walk $p$ of length $\operatorname{dist}(x, y) \ge 3$.

    If $x$ and $y$ were not reachable from one another, their distance would be 0 by convention, contradicting $\operatorname{dist}(x, y) \ge 3$. Hence they are reachable, which yields a walk $p$ from $x$ to $y$ of length equal to $\operatorname{dist}(x, y) \ge 3$.

    lines 10–15

    uses SimpleGraph.dist_eq_zero_of_not_reachable

      have hreach : G.Reachable x y := by
        by_contra hc
        rw [SimpleGraph.dist_eq_zero_of_not_reachable hc] at hd
        omega
      obtain ⟨p, hp⟩ := hreach.exists_walk_length_eq_dist
      have hlen : 3 ≤ p.length := by omega
  3. The first three vertices $p(0) = x$, $p(1)$, and $p(2)$ along $p$ satisfy $x \sim p(1)$ and $p(1) \sim p(2)$.

    Because the walk $p$ has length at least 3, its first two steps exist, and consecutive vertices along any walk are adjacent in $G$.

    lines 16–19

      have h1 : G.Adj x (p.getVert 1) := by
        have := p.adj_getVert_succ (i := 0) (by omega); simpa using this
      have h2 : G.Adj (p.getVert 1) (p.getVert 2) := by
        have := p.adj_getVert_succ (i := 1) (by omega); simpa using this
  4. $x$ is not adjacent to $p(2)$.

    If $x$ were adjacent to $p(2)$, prepending the edge $(x, p(2))$ to the remaining walk from $p(2)$ to $y$ would form a walk from $x$ to $y$ of length $1 + (\operatorname{length}(p) - 2) = \operatorname{length}(p) - 1$. But the distance $\operatorname{dist}(x, y) = \operatorname{length}(p)$ cannot exceed the length of any walk from $x$ to $y$, a contradiction.

    lines 20–25

    uses SimpleGraph.dist_le, SimpleGraph.Walk.cons, SimpleGraph.Walk.length_cons

      have hnadj : ¬ G.Adj x (p.getVert 2) := by
        intro hadj
        have hle := SimpleGraph.dist_le (G := G) (SimpleGraph.Walk.cons hadj (p.drop 2))
        rw [SimpleGraph.Walk.length_cons] at hle
        have h2' : (p.drop 2).length = p.length - 2 := by simp
        omega
  5. $x \ne p(2)$.

    Dropping the first two steps of $p$ gives a walk from $p(2)$ to $y$ of length $\operatorname{length}(p) - 2$, so $\operatorname{dist}(p(2), y) \le \operatorname{length}(p) - 2$. If $x = p(2)$, this would imply $\operatorname{dist}(x, y) \le \operatorname{length}(p) - 2 < \operatorname{length}(p) = \operatorname{dist}(x, y)$, which is impossible.

    lines 26–34

    uses SimpleGraph.dist_le

      have key : ∀ {a : V}, a = p.getVert 2 → G.dist a y ≤ (p.drop 2).length := by
        intro a ha
        rw [ha]
        exact SimpleGraph.dist_le (p.drop 2)
      have hbx : x ≠ p.getVert 2 := by
        intro h
        have hle := key h
        have h2' : (p.drop 2).length = p.length - 2 := by simp
        omega
  6. $\ell + 2 \le k$.

    Applying `simple_graph_card_commonNeighbors_add_two_le_degree` to $u = x$, $w = p(1)$, and $v = p(2)$ in the $k$-regular graph $G$ shows that $|\operatorname{commonNeighbors}(x, p(1))| + 2 \le k$, since $x \ne p(2)$, $x \sim p(1)$, $p(2) \sim p(1)$, and $x \not\sim p(2)$. Ample regularity guarantees that adjacent vertices $x \sim p(1)$ share exactly $\ell$ common neighbors, yielding $\ell + 2 \le k$.

    lines 35–37

    uses simple_graph_card_commonNeighbors_add_two_le_degree

      have hcount := simple_graph_card_commonNeighbors_add_two_le_degree G hG.regular hbx h1 h2.symm hnadj
      have hEll : Fintype.card (G.commonNeighbors x (p.getVert 1)) = ℓ := hG.adj_commonNeighbors h1
      omega
SimpleGraph.nontrivial_of_diam_ne_zero
A graph with non-zero diameter has at least two vertices, so its vertex type is nontrivial.
SimpleGraph.exists_dist_eq_diam
In any nonempty graph, there exists a pair of vertices whose distance equals the graph's diameter.
SimpleGraph.dist_eq_zero_of_not_reachable
If two vertices are not reachable from each other, their graph distance is 0.
SimpleGraph.dist_le
The shortest-path distance between two vertices is at most the length of any walk connecting them.
SimpleGraph.Walk.cons
Prepending an adjacent edge to a walk from $v$ to $w$ yields a walk from $u$ to $w$.
SimpleGraph.Walk.length_cons
Prepending an edge to a walk increases its length by 1.
simple_graph_card_commonNeighbors_add_two_le_degree
In a $k$-regular graph, if $u \ne v$, $w$ is adjacent to both $u$ and $v$, and $u \not\sim v$, 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

/-- Necessary condition for the hard regime: a diameter of at least 3 forces k ≥ ℓ+2, so the bound 2k/(ℓ+2) is at least 2 there and the conjecture cannot be settled by the diam ≤ 2 argument. -/theorem amply_regular_lambda_add_two_le_degree_of_three_le_diam {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]    {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (h3 : 3 ≤ G.diam) :    ℓ + 2 ≤ k := by  classical  have hpos : G.diam ≠ 0 := by omega  have : Nonempty V := (SimpleGraph.nontrivial_of_diam_ne_zero hpos).to_nonempty  obtain ⟨x, y, hxy⟩ := SimpleGraph.exists_dist_eq_diam (G := G)  have hd : 3 ≤ G.dist x y := by omega  have hreach : G.Reachable x y := by    by_contra hc    rw [SimpleGraph.dist_eq_zero_of_not_reachable hc] at hd    omega  obtain ⟨p, hp⟩ := hreach.exists_walk_length_eq_dist  have hlen : 3 ≤ p.length := by omega  have h1 : G.Adj x (p.getVert 1) := by    have := p.adj_getVert_succ (i := 0) (by omega); simpa using this  have h2 : G.Adj (p.getVert 1) (p.getVert 2) := by    have := p.adj_getVert_succ (i := 1) (by omega); simpa using this  have hnadj : ¬ G.Adj x (p.getVert 2) := by    intro hadj    have hle := SimpleGraph.dist_le (G := G) (SimpleGraph.Walk.cons hadj (p.drop 2))    rw [SimpleGraph.Walk.length_cons] at hle    have h2' : (p.drop 2).length = p.length - 2 := by simp    omega  have key : ∀ {a : V}, a = p.getVert 2 → G.dist a y ≤ (p.drop 2).length := by    intro a ha    rw [ha]    exact SimpleGraph.dist_le (p.drop 2)  have hbx : x ≠ p.getVert 2 := by    intro h    have hle := key h    have h2' : (p.drop 2).length = p.length - 2 := by simp    omega  have hcount := simple_graph_card_commonNeighbors_add_two_le_degree G hG.regular hbx h1 h2.symm hnadj  have hEll : Fintype.card (G.commonNeighbors x (p.getVert 1)) = ℓ := hG.adj_commonNeighbors h1  omega
See it in the graphDiscuss this resultChallenge it