AFTD Auto-Formalizing Theoretical Domains

simple_graph_clique_components_independent_iff_injective

theoremverified

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

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.

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

    lines 6–8

      constructor
      · intro h v hv w hw hvw
        by_contra hne
  2. 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.

    lines 9–13

        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
  3. 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.

    line 14

        exact h hv hw hne hadj
  4. If 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.

    lines 15–17

    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

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