amply_regular_lambda_add_two_le_degree_of_three_le_diam
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$.
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$.
uses
SimpleGraph.nontrivial_of_diam_ne_zero,SimpleGraph.exists_dist_eq_diamclassical 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
$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$.
uses
SimpleGraph.dist_eq_zero_of_not_reachablehave 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
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$.
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
$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.
uses
SimpleGraph.dist_le,SimpleGraph.Walk.cons,SimpleGraph.Walk.length_conshave 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
$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.
uses
SimpleGraph.dist_lehave 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
$\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$.
uses
simple_graph_card_commonNeighbors_add_two_le_degreehave 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$.
- In Mathlib's `SimpleGraph`, the distance between vertices in different connected components is defined to be 0 rather than $\infty$. Showing that $\operatorname{dist}(x, y) \ge 3$ implies $x$ and $y$ are connected requires explicitly ruling out the unreachable case via `SimpleGraph.dist_eq_zero_of_not_reachable`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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