AFTD Auto-Formalizing Theoretical Domains

simple_graph_k_independence_number_eq_card_of_degree_lt

theoremverifiedformalization

If every vertex of the finite graph G has degree less than k, then β_k(G) = SF_k(G) = |V(G)|.

Statement

theorem simple_graph_k_independence_number_eq_card_of_degree_lt {V : Type*} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (h : ∀ v, G.degree v < k) :
    simple_graph_k_independence_number G k = Fintype.card V ∧
      simple_graph_upper_k_star_forming_number G k = Fintype.card V
Formalizes
arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Proposition 3.1.
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

The proof, explained

Assuming every vertex of G has degree strictly less than k, the entire vertex set V is k-independent because no vertex has k or more neighbors. Furthermore, V is vacuously k-star-forming, whereas no proper subset of V can be k-star-forming because forming a k-star would require a center of degree at least k; hence V is minimal k-star-forming. Since no subset can exceed |V|, the suprema defining the k-independence number β_k(G) and the upper k-star-forming number SF_k(G) are both attained by V and therefore equal |V|.

  1. The universal vertex set V is k-independent.

    By definition, a set is k-independent if every vertex has strictly fewer than k neighbors in that set. For the full vertex set V (Finset.univ), the set of neighbors of any v ∈ V in Finset.univ is exactly the entire open neighborhood neighborSet v. Rewriting its cardinality into the degree of v, the condition holds immediately from the hypothesis that every vertex has degree strictly less than k.

    lines 5–11

    uses Set.ncard_eq_toFinset_card', G.neighborFinset_def

      have h_ind : simple_graph_is_k_independent G k Finset.univ := by
        intro v _
        have h_set : ({u | u ∈ (univ : Finset V) ∧ G.Adj v u} : Set V) = G.neighborSet v := by
          ext u
          simp
        rw [h_set, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def]
        exact h v
  2. The universal vertex set V is k-star-forming.

    A set S is k-star-forming if every vertex v ∉ S belongs to some star with center and leaves in S ∪ {v}. For S = V (Finset.univ), no vertex lies outside V by Finset.mem_univ, so the condition is vacuously satisfied.

    lines 12–13

    uses Finset.mem_univ

      have h_sf_univ : simple_graph_is_k_star_forming G k Finset.univ :=
        fun v hv => absurd (Finset.mem_univ v) hv
  3. No proper subset of V is k-star-forming.

    Assume for contradiction that some proper subset T ⊂ V is k-star-forming. Since T is a strict subset, there exists a vertex s ∉ T. By the definition of k-star-forming applied to s, there must exist a center c and a set L of k leaves adjacent to c in G. Hence L is a subset of the neighborhood of c, which implies k = |L| ≤ deg(c). But the global hypothesis guarantees deg(c) < k, a contradiction.

    lines 14–25

    uses Finset.exists_of_ssubset, Finset.mem_coe.mp, Set.ncard_le_ncard, Set.toFinite, Set.ncard_coe_finset, Set.ncard_eq_toFinset_card', G.neighborFinset_def

      have h_not_sf : ∀ T ⊂ (univ : Finset V), ¬ simple_graph_is_k_star_forming G k T := by
        intro T hT hsf
        obtain ⟨s, -, hsT⟩ := Finset.exists_of_ssubset hT
        obtain ⟨c, L, -, -, hcard, hadj, -⟩ := hsf s hsT
        have h_sub : (L : Set V) ⊆ G.neighborSet c := by
          intro x hx
          exact hadj x (Finset.mem_coe.mp hx)
        have h_le := Set.ncard_le_ncard h_sub (Set.toFinite (G.neighborSet c))
        rw [Set.ncard_coe_finset, hcard, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def] at h_le
        have h_lt := h c
        change (G.neighborFinset c).card < k at h_lt
        omega
  4. The universal vertex set V is minimal k-star-forming.

    A set is minimal k-star-forming if it is k-star-forming and no strictly smaller subset is k-star-forming. Combining the facts that V is k-star-forming and that no proper subset of V is k-star-forming gives the result.

    lines 26–27

      have h_min_sf : simple_graph_is_minimal_k_star_forming G k Finset.univ :=
        ⟨h_sf_univ, h_not_sf⟩
  5. The k-independence number β_k(G) equals |V|.

    Splitting the conjunction, the first goal is to evaluate β_k(G), the supremum of sizes of k-independent sets. By antisymmetry (le_antisymm): (1) the supremum is at most |V| via csSup_le because the set of sizes is nonempty (witnessed by V of size |V|) and every set of vertices has cardinality at most |V| (card_le_univ); (2) |V| is at most the supremum via le_csSup because the set of sizes is bounded above by |V| and contains |V| (witnessed by V, which is k-independent).

    lines 28–39

    uses le_antisymm, csSup_le, card_univ, card_le_univ, le_csSup

      constructor
      · dsimp [simple_graph_k_independence_number]
        apply le_antisymm
        · apply csSup_le
          · exact ⟨Fintype.card V, univ, h_ind, card_univ⟩
          · rintro n ⟨I, -, rfl⟩
            exact card_le_univ I
        · apply le_csSup
          · refine ⟨Fintype.card V, ?_⟩
            rintro n ⟨I, -, rfl⟩
            exact card_le_univ I
          · exact ⟨univ, h_ind, card_univ⟩
  6. The upper k-star-forming number SF_k(G) equals |V|.

    The second goal is to evaluate SF_k(G), the supremum of sizes of minimal k-star-forming sets. Again by antisymmetry: (1) the supremum is at most |V| via csSup_le because V is a minimal k-star-forming set of size |V| and every subset has size at most |V|; (2) |V| is at most the supremum via le_csSup because the set of sizes is bounded above by |V| and contains |V| as a member.

    lines 40–50

    uses le_antisymm, csSup_le, card_univ, card_le_univ, le_csSup

      · dsimp [simple_graph_upper_k_star_forming_number]
        apply le_antisymm
        · apply csSup_le
          · exact ⟨Fintype.card V, univ, h_min_sf, card_univ⟩
          · rintro n ⟨S, -, rfl⟩
            exact card_le_univ S
        · apply le_csSup
          · refine ⟨Fintype.card V, ?_⟩
            rintro n ⟨S, -, rfl⟩
            exact card_le_univ S
          · exact ⟨univ, h_min_sf, card_univ⟩
Set.ncard_eq_toFinset_card'
For any set s with finite subtype, its set cardinality s.ncard equals the cardinality of its finset representation s.toFinset.card.
G.neighborFinset_def
For any vertex v in G, the finset of its neighbors is by definition the neighborhood set G.neighborSet v converted to a finset.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.exists_of_ssubset
If s₁ ⊂ s₂ is a strict subset, then there exists an element x ∈ s₂ such that x ∉ s₁.
Finset.mem_coe.mp
If an element belongs to the set coercion of a finset, then it belongs to the finset.
Set.ncard_le_ncard
If s ⊆ t and t is finite, then the set cardinality of s is at most the set cardinality of t.
Set.toFinite
A set whose subtype is finite is finite as a set.
Set.ncard_coe_finset
The set cardinality of a coerced finset equals its finset cardinality.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
csSup_le
The supremum of a nonempty set s is at most a if every element of s is at most a.
card_univ
The cardinality of Finset.univ equals Fintype.card α.
card_le_univ
The cardinality of any finset of α is at most Fintype.card α.
le_csSup
If a set s is bounded above, then any element in s is at most the supremum of s.

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_k_independence_number_eq_card_of_degree_lt {V : Type*} [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (h : ∀ v, G.degree v < k) :    simple_graph_k_independence_number G k = Fintype.card V ∧      simple_graph_upper_k_star_forming_number G k = Fintype.card V := open Finset in by  have h_ind : simple_graph_is_k_independent G k Finset.univ := by    intro v _    have h_set : ({u | u ∈ (univ : Finset V) ∧ G.Adj v u} : Set V) = G.neighborSet v := by      ext u      simp    rw [h_set, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def]    exact h v  have h_sf_univ : simple_graph_is_k_star_forming G k Finset.univ :=    fun v hv => absurd (Finset.mem_univ v) hv  have h_not_sf : ∀ T ⊂ (univ : Finset V), ¬ simple_graph_is_k_star_forming G k T := by    intro T hT hsf    obtain ⟨s, -, hsT⟩ := Finset.exists_of_ssubset hT    obtain ⟨c, L, -, -, hcard, hadj, -⟩ := hsf s hsT    have h_sub : (L : Set V) ⊆ G.neighborSet c := by      intro x hx      exact hadj x (Finset.mem_coe.mp hx)    have h_le := Set.ncard_le_ncard h_sub (Set.toFinite (G.neighborSet c))    rw [Set.ncard_coe_finset, hcard, Set.ncard_eq_toFinset_card', ← G.neighborFinset_def] at h_le    have h_lt := h c    change (G.neighborFinset c).card < k at h_lt    omega  have h_min_sf : simple_graph_is_minimal_k_star_forming G k Finset.univ :=    ⟨h_sf_univ, h_not_sf⟩  constructor  · dsimp [simple_graph_k_independence_number]    apply le_antisymm    · apply csSup_le      · exact ⟨Fintype.card V, univ, h_ind, card_univ⟩      · rintro n ⟨I, -, rfl⟩        exact card_le_univ I    · apply le_csSup      · refine ⟨Fintype.card V, ?_⟩        rintro n ⟨I, -, rfl⟩        exact card_le_univ I      · exact ⟨univ, h_ind, card_univ⟩  · dsimp [simple_graph_upper_k_star_forming_number]    apply le_antisymm    · apply csSup_le      · exact ⟨Fintype.card V, univ, h_min_sf, card_univ⟩      · rintro n ⟨S, -, rfl⟩        exact card_le_univ S    · apply le_csSup      · refine ⟨Fintype.card V, ?_⟩        rintro n ⟨S, -, rfl⟩        exact card_le_univ S      · exact ⟨univ, h_min_sf, card_univ⟩
See it in the graphDiscuss this resultChallenge it