simple_graph_is_k_independent_mono
Every subset of a k-independent vertex set is k-independent.
Statement
theorem simple_graph_is_k_independent_mono {V : Type*} (G : SimpleGraph V) (k : ℕ) {I J : Finset V} (hIJ : I ⊆ J) (hJ : simple_graph_is_k_independent G k J) : simple_graph_is_k_independent G k I
- Source
- Monotonicity of k-independence, used in arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination) (Sec. 2 and Proposition 7.1).
- 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 1
- 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).
The proof, explained
The proof shows that any vertex v in the subset I has strictly fewer than k neighbors in I. Since I ⊆ J, the set of neighbors of v in I is contained in the set of neighbors of v in J. Because J is finite, the number of neighbors in I is at most the number of neighbors in J, which is strictly less than k by the k-independence of J.
To show that I is k-independent, it suffices to show that each vertex v ∈ I has strictly fewer than k neighbors in I.
By definition, a vertex set I is k-independent in G if every vertex v ∈ I has strictly fewer than k neighbors in I. We fix an arbitrary vertex v and assume v ∈ I.
intro v hvThe vertex v has strictly fewer than k neighbors in I.
Every neighbor of v in I is also a neighbor of v in J because I ⊆ J, so {u ∈ I | G.Adj v u} ⊆ {u ∈ J | G.Adj v u}. Since J is finite, this superset of neighbors is finite, and Set.ncard_le_ncard gives that v has at most as many neighbors in I as in J. Moreover, because v ∈ I ⊆ J, the k-independence of J implies that v has strictly fewer than k neighbors in J. Transitivity of ≤ and < via lt_of_le_of_lt concludes that v has strictly fewer than k neighbors in I.
uses
lt_of_le_of_lt,Set.ncard_le_ncardrefine lt_of_le_of_lt (Set.ncard_le_ncard ?_ (J.finite_toSet.subset (fun w hw => hw.1))) (hJ v (hIJ hv)) exact fun w hw => ⟨hIJ hw.1, hw.2⟩
lt_of_le_of_lt- In a preorder, if a ≤ b and b < c, then a < c.
Set.ncard_le_ncard- If s ⊆ t and t is finite, then the cardinality of s is at most the cardinality of t.
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_mono {V : Type*} (G : SimpleGraph V) (k : ℕ) {I J : Finset V} (hIJ : I ⊆ J) (hJ : simple_graph_is_k_independent G k J) : simple_graph_is_k_independent G k I := open Finset in by intro v hv refine lt_of_le_of_lt (Set.ncard_le_ncard ?_ (J.finite_toSet.subset (fun w hw => hw.1))) (hJ v (hIJ hv)) exact fun w hw => ⟨hIJ hw.1, hw.2⟩