simple_graph_is_k_independent_iff
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
- exists_triangle_free_k_independence_number_lt_upper_k_star_forming_numberThere is a triangle-free graph H on 10 vertices with β_4(H) = 7 < 8 = SF_4(H).
- simple_graph_k_independence_number_le_upper_k_star_forming_numberFor every finite graph G and every k, β_k(G) ≤ SF_k(G).
- complete_bipartite_k_independence_number_eq_upper_k_star_forming_numberFor k ≥ 2 and a, b ≥ k, the complete bipartite graph K_{a,b} has β_k(K_{a,b}) = SF_k(K_{a,b}) = max{a, b, 2k − 2}.
- chain_graph_two_independence_number_eq_upper_two_star_forming_numberFor every finite chain graph G, the dissociation number β₂(G) equals the upper 2-star-forming number SF₂(G).
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.
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$.
unfold simple_graph_is_k_independentFor 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)\}$.
uses
Set.ncard_coe_finset,coe_filterhave : ∀ 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]
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.
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
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.
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]