simple_graph_clique_components_independent_iff_injective
In a graph whose connected components are cliques, a set is independent exactly when the component map is injective on it.
Statement
theorem simple_graph_clique_components_independent_iff_injective {V : Type*} (G : SimpleGraph V) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (s : Set V) : G.IsIndepSet s ↔ s.InjOn G.connectedComponentMk
- 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
To show that a set s is independent if and only if the connected component map is injective on s when every component is a clique, we argue in both directions. In the forward direction, if two distinct vertices in s shared a component, that component's clique structure would force them to be adjacent, contradicting independence. In the reverse direction, any edge between vertices in s would put them in the same component, contradicting injectivity.
To show that independence implies injectivity, consider two vertices v, w ∈ s in the same connected component and assume for contradiction that v ≠ w.
We split the equivalence into two directions. For the forward direction, assuming s is an independent set, we take two vertices v, w ∈ s mapped to the same connected component and assume for contradiction that they are distinct.
constructor · intro h v hv w hw hvw by_contra hne
v and w are adjacent in G.
Let c be the connected component of v. Since v and w map to the same component, both belong to the support of c. By assumption, every connected component induces a clique, so the two distinct vertices v and w in c are adjacent.
have hadj : G.Adj v w := by let c := G.connectedComponentMk v have hvc : v ∈ c.supp := (c.mem_supp_iff v).mpr rfl have hwc : w ∈ c.supp := (c.mem_supp_iff w).mpr hvw.symm exact hclique c hvc hwc hne
The assumption v ≠ w yields a contradiction, so v = w and the component map is injective on s.
Because s is an independent set, no two distinct vertices in s can be adjacent. This contradicts the fact that v and w are adjacent.
exact h hv hw hne hadjIf the component map is injective on s, then s is an independent set.
To show s is independent, assume for contradiction that there are distinct vertices v, w ∈ s that are adjacent. By SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj, adjacent vertices belong to the same connected component. Then injectivity of the component map on s implies v = w, contradicting v ≠ w.
uses
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj· intro h v hv w hw hne hadj have heq := SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj hadj exact hne (h hv hw heq)
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj- If two vertices in a simple graph are adjacent, they belong to the same connected component.
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_independent_iff_injective {V : Type*} (G : SimpleGraph V) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (s : Set V) : G.IsIndepSet s ↔ s.InjOn G.connectedComponentMk := by constructor · intro h v hv w hw hvw by_contra hne have hadj : G.Adj v w := by let c := G.connectedComponentMk v have hvc : v ∈ c.supp := (c.mem_supp_iff v).mpr rfl have hwc : w ∈ c.supp := (c.mem_supp_iff w).mpr hvw.symm exact hclique c hvc hwc hne exact h hv hw hne hadj · intro h v hv w hw hne hadj have heq := SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj hadj exact hne (h hv hw heq)