AFTD Auto-Formalizing Theoretical Domains

simple_graph_clique_components_closed_neighborhood

theoremverified

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

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.

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

    lines 8–11

    uses Finset.mem_insert, SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, true_and

      classical
      ext u
      simp only [Finset.mem_insert, SimpleGraph.mem_neighborFinset, Finset.mem_filter,
        Finset.mem_univ, true_and]
  2. 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`.

    lines 12–15

    uses SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj

      constructor
      · rintro (rfl | h)
        · rfl
        · exact (SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj h).symm
  3. 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.

    lines 16–23

    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.

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

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