AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_star_forming_univ

theoremverified

In a finite graph the whole vertex set is k-star-forming, for every k (there is no vertex outside it).

Statement

theorem simple_graph_is_k_star_forming_univ {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) :
    simple_graph_is_k_star_forming G k Finset.univ
Source
Sanity lemma for the definition of k-star-forming sets, 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_star_formingA vertex set S is k-star-forming when, for every vertex v outside S, the induced graph G[S ∪ {v}] contains a copy of the star K_{1,k} that…
Used by 1

The proof, explained

The property of being k-star-forming requires a certain condition for every vertex outside the given set S. When S is the full vertex set Finset.univ, there are no vertices outside S, as every vertex belongs to Finset.univ. The condition is therefore vacuously satisfied.

  1. The universal set Finset.univ is vacuously k-star-forming for any k.

    By definition, a vertex set S is k-star-forming if every vertex v ∉ S can be extended to a k-star. For S = Finset.univ, suppose there were some vertex v ∉ Finset.univ (hv). But by Finset.mem_univ, every vertex v of the finite type V belongs to Finset.univ, which directly contradicts hv. From this contradiction, the condition holds vacuously.

    line 3

    uses Finset.mem_univ

      intro v hv; exact absurd (Finset.mem_univ v) hv
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.

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_star_forming_univ {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) :    simple_graph_is_k_star_forming G k Finset.univ := by  intro v hv; exact absurd (Finset.mem_univ v) hv
See it in the graphDiscuss this resultChallenge it