simple_graph_common_neighbors_card_le_degree_sub_one
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.
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).
uses
Finset.mem_inter,SimpleGraph.mem_neighborFinset,Finset.mem_erase,G.irreflhave 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
|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.
uses
Finset.card_le_card,Finset.card_erase_of_mem,G.card_neighborFinset_eq_degreecalc (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
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.
/-- 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]