simple_graph_is_k_independent_empty
The empty vertex set is k-independent, for every k.
Statement
theorem simple_graph_is_k_independent_empty {V : Type*} (G : SimpleGraph V) (k : ℕ) : simple_graph_is_k_independent G k ∅
- Source
- Sanity lemma for the definition of k-independence, arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination).
- 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
- simple_graph_k_independence_number_le_upper_k_star_forming_numberFor every finite graph G and every k, β_k(G) ≤ SF_k(G).
The proof, explained
The theorem is proved by vacuous truth. By definition, a subset of vertices is $k$-independent if each of its vertices has fewer than $k$ neighbors in the subset. Since the empty set contains no vertices, this condition holds trivially.
The neighborhood cardinality condition holds vacuously for all vertices in the empty set.
By definition, a vertex set is $k$-independent if every vertex in the set has strictly fewer than $k$ neighbors within the set. Assuming there is a vertex $v \in \emptyset$ (introduced as `hv`), the simplifier recognizes that the empty set has no elements, turning the assumption into `False` and completing the proof by contradiction.
intro v hv; simp at hv
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_empty {V : Type*} (G : SimpleGraph V) (k : ℕ) : simple_graph_is_k_independent G k ∅ := by intro v hv; simp at hv