AFTD Auto-Formalizing Theoretical Domains

simple_graph_common_neighbors_card_le_degree_sub_one

theoremverified

The number of common neighbors of two adjacent vertices u and v is at most deg(u) - 1.

Statement

theorem simple_graph_common_neighbors_card_le_degree_sub_one {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {u v : V} (h : G.Adj u v) :
    (G.neighborFinset u ∩ G.neighborFinset v).card ≤ G.degree u - 1
Source
step towards simple_graph_triangle_cover_number_le_two_mul_packing_number_of_max_degree_le_eleven
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To bound the number of common neighbors of two adjacent vertices u and v, the proof first shows that every common neighbor is a neighbor of u other than v, since simple graphs contain no self-loops. This yields the set inclusion N(u) ∩ N(v) ⊆ N(u) \ {v}. The desired bound then follows by taking cardinalities: since u and v are adjacent, v is a neighbor of u, so removing v decreases the cardinality of N(u) by one, leaving deg(u) - 1.

  1. N(u) ∩ N(v) ⊆ N(u) \ {v}

    Let w be an arbitrary common neighbor in N(u) ∩ N(v). By definition of intersection and neighbor sets (Finset.mem_inter, SimpleGraph.mem_neighborFinset), w is adjacent to both u and v. To show that w belongs to N(u) with v removed (Finset.mem_erase), we must show that w ≠ v and that w is adjacent to u. The adjacency to u is already known. If w = v, then v would be adjacent to itself, which contradicts the irreflexivity of simple graphs (G.irrefl).

    lines 5–11

    uses Finset.mem_inter, SimpleGraph.mem_neighborFinset, Finset.mem_erase, G.irrefl

      have hsub : G.neighborFinset u ∩ G.neighborFinset v ⊆ (G.neighborFinset u).erase v := by
        intro w hw
        rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset, SimpleGraph.mem_neighborFinset] at hw
        rw [Finset.mem_erase, SimpleGraph.mem_neighborFinset]
        refine ⟨?_, hw.1⟩
        rintro rfl
        exact G.irrefl hw.2
  2. |N(u) ∩ N(v)| ≤ |N(u) \ {v}| = deg(u) - 1

    By monotonicity of finite set cardinality (Finset.card_le_card), the inclusion N(u) ∩ N(v) ⊆ N(u) \ {v} gives |N(u) ∩ N(v)| ≤ |N(u) \ {v}|. Because u and v are adjacent (h), v is an element of N(u), so erasing v decreases the cardinality of N(u) by one (Finset.card_erase_of_mem). Finally, the cardinality of N(u) is the degree deg(u) (G.card_neighborFinset_eq_degree), yielding the bound |N(u) ∩ N(v)| ≤ deg(u) - 1.

    lines 12–17

    uses Finset.card_le_card, Finset.card_erase_of_mem, G.card_neighborFinset_eq_degree

      calc
        (G.neighborFinset u ∩ G.neighborFinset v).card ≤ ((G.neighborFinset u).erase v).card :=
          Finset.card_le_card hsub
        _ = (G.neighborFinset u).card - 1 := by
          rw [Finset.card_erase_of_mem (by simpa using h)]
        _ = G.degree u - 1 := by rw [G.card_neighborFinset_eq_degree]
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
SimpleGraph.mem_neighborFinset
A vertex belongs to the neighbor finset of another vertex if and only if the two vertices are adjacent in the graph.
Finset.mem_erase
An element belongs to a finite set with an element removed if and only if it is distinct from that element and belongs to the original set.
G.irrefl
In a simple graph, no vertex is adjacent to itself (adjacency is irreflexive).
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the other set.
Finset.card_erase_of_mem
Removing an element from a finite set that contains it decreases the cardinality of the set by one.
G.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex equals its degree.

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

/-- The number of common neighbors of two adjacent vertices u and v is at most deg(u) - 1. -/theorem simple_graph_common_neighbors_card_le_degree_sub_one {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] {u v : V} (h : G.Adj u v) :    (G.neighborFinset u ∩ G.neighborFinset v).card ≤ G.degree u - 1 := by  have hsub : G.neighborFinset u ∩ G.neighborFinset v ⊆ (G.neighborFinset u).erase v := by    intro w hw    rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset, SimpleGraph.mem_neighborFinset] at hw    rw [Finset.mem_erase, SimpleGraph.mem_neighborFinset]    refine ⟨?_, hw.1⟩    rintro rfl    exact G.irrefl hw.2  calc    (G.neighborFinset u ∩ G.neighborFinset v).card ≤ ((G.neighborFinset u).erase v).card :=      Finset.card_le_card hsub    _ = (G.neighborFinset u).card - 1 := by      rw [Finset.card_erase_of_mem (by simpa using h)]    _ = G.degree u - 1 := by rw [G.card_neighborFinset_eq_degree]
See it in the graphDiscuss this resultChallenge it