amply_regular_mu_le_degree_of_dist_two
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.
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.
uses
SimpleGraph.mem_commonNeighborshave hsub : G.commonNeighbors u v ⊆ G.neighborSet u := by intro w hw rw [SimpleGraph.mem_commonNeighbors] at hw exact hw.1
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.
uses
Fintype.card_le_of_injective,congrArghave 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
μ ≤ 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.
uses
SimpleGraph.card_neighborSet_eq_degreerw [← 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.
- On paper, the inequality |G.commonNeighbors u v| ≤ |G.neighborSet u| follows immediately from the subset inclusion G.commonNeighbors u v ⊆ G.neighborSet u. In Lean, this is formalized in lines 10–13 by explicitly defining an injection between the subtype of common neighbors and the subtype of neighbors, and proving its injectivity using subtype extensionality and congrArg.
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.
/-- 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