AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_independent_mono

theoremverified

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

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.

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

    line 4

      intro v hv
  2. The 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.

    lines 5–7

    uses lt_of_le_of_lt, Set.ncard_le_ncard

      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⟩
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

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