AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_independent_iff

theoremverified

With decidable adjacency, a vertex set I is k-independent iff every v ∈ I has fewer than k neighbours in the finset I.filter (G.Adj v).

Statement

theorem simple_graph_is_k_independent_iff {V : Type*} [DecidableEq V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (k : ℕ) (I : Finset V) :
    simple_graph_is_k_independent G k I ↔ ∀ v ∈ I, (I.filter (G.Adj v)).card < k
Source
Computable form of k-independence for arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination) (used for Proposition 7.1 and Theorem 3.2).
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_is_k_independentA vertex set I of a graph G is k-independent when the induced subgraph G[I] has maximum degree less than k: every vertex of I has fewer…
Used by 4

The proof, explained

By definition, a finset $I$ is $k$-independent in a graph $G$ if for each vertex $v \in I$, the set of neighbors of $v$ belonging to $I$, $\{u \in I \mid G.\text{Adj}(v, u)\}$, has set cardinality strictly less than $k$. The theorem establishes that this condition is equivalent to the finset filter $I.\text{filter}(G.\text{Adj}(v))$ having cardinality strictly less than $k$. The proof unfolds the definition of $k$-independence, shows that the set-theoretic cardinality equals the finset filter cardinality by coercing the finset to a set, and substitutes this equality into the equivalence.

  1. The definition of $k$-independence is expanded into a condition on set cardinality.

    Unfolding the definition `simple_graph_is_k_independent` reformulates the left-hand side as the condition that for every $v \in I$, the set cardinality of $\{u \in V \mid u \in I \wedge G.\text{Adj}(v, u)\}$ is strictly less than $k$.

    line 4

      unfold simple_graph_is_k_independent
  2. For every vertex $v$, the set cardinality of $\{u \in V \mid u \in I \wedge G.\text{Adj}(v, u)\}$ equals the finset cardinality of $I.\text{filter}(G.\text{Adj}(v))$.

    Fixing an arbitrary vertex $v$, the finset cardinality of $I.\text{filter}(G.\text{Adj}(v))$ is rewritten into the cardinality of its coerced set using `Set.ncard_coe_finset`. Then, `coe_filter` identifies the coerced finset with the set comprehension $\{u \in V \mid u \in I \wedge G.\text{Adj}(v, u)\}$.

    lines 5–7

    uses Set.ncard_coe_finset, coe_filter

      have : ∀ v, ({u | u ∈ I ∧ G.Adj v u} : Set V).ncard = (I.filter (G.Adj v)).card := by
        intro v
        rw [← Set.ncard_coe_finset, coe_filter]
  3. A vertex set $I$ is $k$-independent if and only if each $v \in I$ has fewer than $k$ neighbors in $I$.filter $(G.\text{Adj}(v))$.

    Rewriting the goal with the established equality of cardinalities makes both sides of the equivalence identical, which completes the proof.

    line 8

      simp only [this]
Set.ncard_coe_finset
The set cardinality (`Set.ncard`) of a coerced finite set is equal to its finset cardinality (`Finset.card`).
coe_filter
The coercion of a filtered finset `Finset.filter p s` to a set is the set comprehension `{x | x ∈ s ∧ p x}`.

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

theorem simple_graph_is_k_independent_iff {V : Type*} [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (k : ℕ) (I : Finset V) :    simple_graph_is_k_independent G k I ↔ ∀ v ∈ I, (I.filter (G.Adj v)).card < k := open Finset in by  unfold simple_graph_is_k_independent  have : ∀ v, ({u | u ∈ I ∧ G.Adj v u} : Set V).ncard = (I.filter (G.Adj v)).card := by    intro v    rw [← Set.ncard_coe_finset, coe_filter]  simp only [this]
See it in the graphDiscuss this resultChallenge it