simple_graph_clique_components_closed_neighborhood
In a graph whose connected components are cliques, a vertex closed neighborhood is its connected-component fiber.
Statement
theorem simple_graph_clique_components_closed_neighborhood {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (v : V) : insert v (G.neighborFinset v) = Finset.univ.filter (fun u => G.connectedComponentMk u = G.connectedComponentMk v)
- Source
- Component decomposition for op_1355_clique_components_variance_ge_bound.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_1355_clique_components_variance_ge_boundFor any finite simple graph G on a finite type V with decidable equality whose connected components are all cliques, and for all positive…
The proof, explained
The theorem shows that when every connected component of a graph is a clique, the closed neighborhood of a vertex v is exactly the fiber of vertices in the same connected component as v. By extensionality, this reduces to showing that a vertex u is adjacent to or equal to v if and only if u and v share the same connected component. The forward direction holds because equality and adjacency both imply belonging to the same component. The reverse direction splits on whether u = v: identical vertices are in the closed neighborhood trivially, while distinct vertices in the same component must be adjacent by the clique hypothesis.
The set equality reduces by extensionality to showing that for every vertex u, u = v or v is adjacent to u if and only if u and v have the same connected component.
By set extensionality (`ext u`), two finsets are equal if they contain the same vertices. An element u belongs to insert v (G.neighborFinset v) if and only if u = v or G.Adj v u, by `Finset.mem_insert` and `SimpleGraph.mem_neighborFinset`. Similarly, u belongs to the filtered universal finset if and only if G.connectedComponentMk u = G.connectedComponentMk v, by `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`.
uses
Finset.mem_insert,SimpleGraph.mem_neighborFinset,Finset.mem_filter,Finset.mem_univ,true_andclassical ext u simp only [Finset.mem_insert, SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, true_and]
Every vertex in the closed neighborhood of v belongs to the connected component of v.
Splitting the iff into two implications (`constructor`), we assume u is in the closed neighborhood (`rintro (rfl | h)`). If u = v, their connected components are trivially identical by reflexivity (`rfl`). If v and u are adjacent (hypothesis `h`), they belong to the same connected component by `SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj`.
uses
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adjconstructor · rintro (rfl | h) · rfl · exact (SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj h).symm
Conversely, every vertex in the connected component of v belongs to the closed neighborhood of v.
Assume u and v belong to the same connected component c (`intro h`). If u = v, then u is in the closed neighborhood via the left disjunct (`Or.inl`). If u ≠ v, it suffices to show v and u are adjacent (`right`). Both v and u lie in the support c.supp of component c. Because every component is assumed to be a clique (`hclique`), any two distinct vertices in c.supp are adjacent; since v ≠ u by symmetry (`Ne.symm`), v and u are adjacent, placing u in the neighbor set of v.
uses
Or.inl,Ne.symm· intro h by_cases huv : u = v · exact Or.inl huv · right let c := G.connectedComponentMk v have hvc : v ∈ c.supp := (c.mem_supp_iff v).mpr rfl have huc : u ∈ c.supp := (c.mem_supp_iff u).mpr h exact hclique c hvc huc (Ne.symm huv)
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The conjunction True ∧ p is equivalent to p.
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj- Adjacent vertices belong to the same connected component.
Or.inl- From a proof of A, deduce the disjunction A ∨ B.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
- In Lean, a connected component c is a bundled structure whose underlying vertex set is c.supp; on paper, one identifies the component directly with its set of vertices.
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.
open scoped Classicaltheorem simple_graph_clique_components_closed_neighborhood {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (v : V) : insert v (G.neighborFinset v) = Finset.univ.filter (fun u => G.connectedComponentMk u = G.connectedComponentMk v) := by classical ext u simp only [Finset.mem_insert, SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, true_and] constructor · rintro (rfl | h) · rfl · exact (SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj h).symm · intro h by_cases huv : u = v · exact Or.inl huv · right let c := G.connectedComponentMk v have hvc : v ∈ c.supp := (c.mem_supp_iff v).mpr rfl have huc : u ∈ c.supp := (c.mem_supp_iff u).mpr h exact hclique c hvc huc (Ne.symm huv)