simple_graph_is_k_star_forming_mono
Every superset of a k-star-forming set is k-star-forming.
Statement
theorem simple_graph_is_k_star_forming_mono {V : Type*} (G : SimpleGraph V) (k : ℕ) {S T : Finset V} (hST : S ⊆ T) (hS : simple_graph_is_k_star_forming G k S) : simple_graph_is_k_star_forming G k T
- Source
- Monotonicity used implicitly in arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination) (Lemma 2.2 and the minimality arguments).
- 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 2
- exists_triangle_free_k_independence_number_lt_upper_k_star_forming_numberThere is a triangle-free graph H on 10 vertices with β_4(H) = 7 < 8 = SF_4(H).
- complete_bipartite_k_independence_number_eq_upper_k_star_forming_numberFor k ≥ 2 and a, b ≥ k, the complete bipartite graph K_{a,b} has β_k(K_{a,b}) = SF_k(K_{a,b}) = max{a, b, 2k − 2}.
The proof, explained
To show that any superset T of a k-star-forming set S is also k-star-forming, take any vertex v ∉ T. Because S ⊆ T, v also lies outside S, so by hypothesis there is a k-star containing v whose center and leaves lie in {v} ∪ S. Since S ⊆ T, these vertices also lie in {v} ∪ T, fulfilling the definition for T.
Fix an arbitrary vertex v ∉ T
To show that T is k-star-forming, let v be any vertex not in T.
intro v hvThere exist a center c and a leaf set L forming a k-star at v with vertices in {v} ∪ S
Since S ⊆ T and v ∉ T, we have v ∉ S. Applying the k-star-forming property of S to v yields a center c and a leaf set L of size k such that all vertices belong to {v} ∪ S, each leaf is adjacent to c, and v is either c or one of the leaves.
obtain ⟨c, L, hc, hL, hcard, hadj, hvc⟩ := hS v (fun h => hv (hST h))
The pair (c, L) satisfies the k-star-forming conditions for T
Since S ⊆ T, any vertex in {v} ∪ S is also in {v} ∪ T. Using Or.imp_right on the memberships hc and hL shows c ∈ {v} ∪ T and L ⊆ {v} ∪ T, while the cardinality, adjacency, and incidence conditions remain identical.
uses
Or.imp_rightexact ⟨c, L, hc.imp_right (fun h => hST h), fun x hx => (hL x hx).imp_right (fun h => hST h), hcard, hadj, hvc⟩
Or.imp_right- if b implies c, then a ∨ b implies a ∨ c
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_mono {V : Type*} (G : SimpleGraph V) (k : ℕ) {S T : Finset V} (hST : S ⊆ T) (hS : simple_graph_is_k_star_forming G k S) : simple_graph_is_k_star_forming G k T := by intro v hv obtain ⟨c, L, hc, hL, hcard, hadj, hvc⟩ := hS v (fun h => hv (hST h)) exact ⟨c, L, hc.imp_right (fun h => hST h), fun x hx => (hL x hx).imp_right (fun h => hST h), hcard, hadj, hvc⟩