simple_graph_is_k_star_forming_univ
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
- simple_graph_k_independence_number_eq_card_of_degree_ltIf every vertex of the finite graph G has degree less than k, then β_k(G) = SF_k(G) = |V(G)|.
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.
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.
uses
Finset.mem_univintro 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
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_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