AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_independent_empty

theoremverified

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

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.

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

    line 3

      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

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