simple_graph_card_commonNeighbors_add_two_le_degree
Let 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 not adjacent to v, then u and w have at most k - 2 common neighbours: |N(u) ∩ N(w)| + 2 ≤ k.
Statement
theorem simple_graph_card_commonNeighbors_add_two_le_degree {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hreg : G.IsRegularOfDegree k) {u v w : V} (hne : u ≠ v) (huw : G.Adj u w) (hvw : G.Adj v w) (huv : ¬ G.Adj u v) : Fintype.card (G.commonNeighbors u w) + 2 ≤ k
- Source
- step towards amply_regular_diameter_bound_conjecture
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- amply_regular_lambda_add_two_le_degree_of_three_le_diamAn amply regular graph with parameters (k, ℓ, μ) whose diameter is at least 3 satisfies ℓ + 2 ≤ k. (Equivalently: if k ≤ ℓ + 1 then the…
- amply_regular_diameter_bound_of_diam_le_twoAn amply regular graph with parameters (k, ℓ, μ) whose diameter is at most 2 has diameter at most 2k/(ℓ+2). No hypothesis on μ is needed:…
The proof, explained
The common neighborhood N(u) ∩ N(w) is contained in N(w) \ {u} because simple graphs have no self-loops. Assuming for contradiction that |N(u) ∩ N(w)| + 2 > k, the cardinality of the intersection must be at least k - 1 = |N(w) \ {u}|, forcing this subset inclusion to be an equality between sets of size k - 1. But v is a neighbor of w distinct from u, so v ∈ N(w) \ {u} = N(u) ∩ N(w), which implies u and v are adjacent, contradicting the hypothesis that they are non-adjacent.
The neighbor finsets of both u and w have cardinality k.
Because G is regular of degree k, every vertex has degree k. Since the size of the neighbor finset of a vertex equals its degree, both |N(u)| = k and |N(w)| = k.
uses
SimpleGraph.card_neighborFinset_eq_degreeclassical have hFk : (G.neighborFinset u).card = k := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg u have hWk : (G.neighborFinset w).card = k := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg w
The common neighborhood of u and w is the intersection N(u) ∩ N(w), and the membership relations of u and v in these neighbor sets are established.
By definition of common neighbors, a vertex belongs to the common neighborhood of u and w if and only if it is adjacent to both, so the common neighborhood is the finite set intersection N(u) ∩ N(w). By adjacency and symmetry of edges, u, v ∈ N(w). Since u is not adjacent to v, v ∉ N(u), and since simple graphs have no self-loops, u ∉ N(u).
uses
SimpleGraph.mem_neighborFinset,SimpleGraph.mem_commonNeighborshave hCeq : (G.commonNeighbors u w).toFinset = G.neighborFinset u ∩ G.neighborFinset w := by ext x; simp [SimpleGraph.mem_neighborFinset, SimpleGraph.mem_commonNeighbors] have huW : u ∈ G.neighborFinset w := by rw [SimpleGraph.mem_neighborFinset]; exact huw.symm have hvW : v ∈ G.neighborFinset w := by rw [SimpleGraph.mem_neighborFinset]; exact hvw.symm have hvF : v ∉ G.neighborFinset u := by rw [SimpleGraph.mem_neighborFinset]; exact huv have huF : u ∉ G.neighborFinset u := by simp
It suffices to show that |N(u) ∩ N(w)| + 2 ≤ |N(u)|.
The number of common neighbors |N(u, w)| is the cardinality of N(u) ∩ N(w), and |N(u)| = k. Therefore, establishing |N(u) ∩ N(w)| + 2 ≤ |N(u)| immediately implies the target inequality |N(u, w)| + 2 ≤ k.
uses
Set.toFinset_cardsuffices h : (G.neighborFinset u ∩ G.neighborFinset w).card + 2 ≤ (G.neighborFinset u).card by rw [← Set.toFinset_card, hCeq]; omega
Assume for contradiction that |N(u)| < |N(u) ∩ N(w)| + 2.
We argue by contradiction. Negating the target inequality |N(u) ∩ N(w)| + 2 ≤ |N(u)| yields |N(u)| < |N(u) ∩ N(w)| + 2.
by_contra hcon push Not at hcon
The intersection N(u) ∩ N(w) is a subset of N(w) \ {u}.
Every vertex x ∈ N(u) ∩ N(w) is adjacent to u. Because graphs have no self-loops (u ∉ N(u)), x cannot be u. Thus x ∈ N(w) and x ≠ u, so x ∈ N(w) \ {u}.
uses
Finset.mem_inter,Finset.mem_erase.mprhave hCsub2 : G.neighborFinset u ∩ G.neighborFinset w ⊆ (G.neighborFinset w).erase u := by intro x hx rw [Finset.mem_inter] at hx exact Finset.mem_erase.mpr ⟨fun hh => huF (hh ▸ hx.1), hx.2⟩
The subset inclusion is an equality: N(u) ∩ N(w) = N(w) \ {u}.
Because u ∈ N(w), removing u from N(w) gives a set of size |N(w)| - 1 = k - 1. Under the contradictory assumption |N(u)| < |N(u) ∩ N(w)| + 2 with |N(u)| = k, linear arithmetic forces |N(u) ∩ N(w)| ≥ k - 1. Since N(u) ∩ N(w) ⊆ N(w) \ {u} and its cardinality is at least that of N(w) \ {u}, the two sets must be equal.
uses
Finset.eq_of_subset_of_card_le,Finset.card_erase_of_memhave hset2 : G.neighborFinset u ∩ G.neighborFinset w = (G.neighborFinset w).erase u := Finset.eq_of_subset_of_card_le hCsub2 (by rw [Finset.card_erase_of_mem huW, hWk]; omega)
The vertex v must belong to N(u), producing a contradiction.
Because v is a neighbor of w distinct from u, it belongs to N(w) \ {u}. By the set equality from the previous step, v must belong to N(u) ∩ N(w), which implies v ∈ N(u). But this contradicts the hypothesis that u and v are non-adjacent.
uses
Finset.mem_erase.mpr,Finset.mem_inter.mphave hv : v ∈ G.neighborFinset u ∩ G.neighborFinset w := by rw [hset2]; exact Finset.mem_erase.mpr ⟨hne.symm, hvW⟩ exact hvF (Finset.mem_inter.mp hv).1
SimpleGraph.card_neighborFinset_eq_degree- In a simple graph, the cardinality of the neighbor finset of a vertex equals its degree.
SimpleGraph.mem_neighborFinset- A vertex belongs to the neighbor finset of v if and only if it is adjacent to v.
SimpleGraph.mem_commonNeighbors- A vertex belongs to the common neighborhood of u and v if and only if it is adjacent to both u and v.
Set.toFinset_card- The cardinality of the finset coercion of a finite set equals its cardinality as a finite type.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_erase.mpr- If x ≠ a and x ∈ s, then x belongs to the set s \ {a} obtained by removing a from s.
Finset.eq_of_subset_of_card_le- If a finite set s is a subset of t and |t| ≤ |s|, then s = t.
Finset.card_erase_of_mem- Removing an element a from a finite set s that contains it decreases the cardinality by 1: |s \ {a}| = |s| - 1.
Finset.mem_inter.mp- If an element belongs to the intersection of two finite sets, it belongs to the first set and to the second set.
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.
/-- Counting lemma for regular graphs: two non-adjacent neighbours u, v of w cannot both lie in N(u) ∩ N(w), so N(u) ∩ N(w) misses the two distinct points u, v of N(w). -/theorem simple_graph_card_commonNeighbors_add_two_le_degree {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (hreg : G.IsRegularOfDegree k) {u v w : V} (hne : u ≠ v) (huw : G.Adj u w) (hvw : G.Adj v w) (huv : ¬ G.Adj u v) : Fintype.card (G.commonNeighbors u w) + 2 ≤ k := by classical have hFk : (G.neighborFinset u).card = k := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg u have hWk : (G.neighborFinset w).card = k := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg w have hCeq : (G.commonNeighbors u w).toFinset = G.neighborFinset u ∩ G.neighborFinset w := by ext x; simp [SimpleGraph.mem_neighborFinset, SimpleGraph.mem_commonNeighbors] have huW : u ∈ G.neighborFinset w := by rw [SimpleGraph.mem_neighborFinset]; exact huw.symm have hvW : v ∈ G.neighborFinset w := by rw [SimpleGraph.mem_neighborFinset]; exact hvw.symm have hvF : v ∉ G.neighborFinset u := by rw [SimpleGraph.mem_neighborFinset]; exact huv have huF : u ∉ G.neighborFinset u := by simp suffices h : (G.neighborFinset u ∩ G.neighborFinset w).card + 2 ≤ (G.neighborFinset u).card by rw [← Set.toFinset_card, hCeq]; omega by_contra hcon push Not at hcon have hCsub2 : G.neighborFinset u ∩ G.neighborFinset w ⊆ (G.neighborFinset w).erase u := by intro x hx rw [Finset.mem_inter] at hx exact Finset.mem_erase.mpr ⟨fun hh => huF (hh ▸ hx.1), hx.2⟩ have hset2 : G.neighborFinset u ∩ G.neighborFinset w = (G.neighborFinset w).erase u := Finset.eq_of_subset_of_card_le hCsub2 (by rw [Finset.card_erase_of_mem huW, hWk]; omega) have hv : v ∈ G.neighborFinset u ∩ G.neighborFinset w := by rw [hset2]; exact Finset.mem_erase.mpr ⟨hne.symm, hvW⟩ exact hvF (Finset.mem_inter.mp hv).1