AFTD Auto-Formalizing Theoretical Domains

simple_graph_card_commonNeighbors_add_two_le_degree

theoremverified

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

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.

  1. 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.

    lines 6–10

    uses SimpleGraph.card_neighborFinset_eq_degree

      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
  2. 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).

    lines 11–16

    uses SimpleGraph.mem_neighborFinset, SimpleGraph.mem_commonNeighbors

      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
  3. 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.

    lines 17–18

    uses Set.toFinset_card

      suffices h : (G.neighborFinset u ∩ G.neighborFinset w).card + 2 ≤ (G.neighborFinset u).card by
        rw [← Set.toFinset_card, hCeq]; omega
  4. 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.

    lines 19–20

      by_contra hcon
      push Not at hcon
  5. 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}.

    lines 21–24

    uses Finset.mem_inter, Finset.mem_erase.mpr

      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⟩
  6. 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.

    lines 25–26

    uses Finset.eq_of_subset_of_card_le, Finset.card_erase_of_mem

      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)
  7. 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.

    lines 27–29

    uses Finset.mem_erase.mpr, Finset.mem_inter.mp

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it