simple_graph_is_k_star_forming_iff
For k ≥ 1, a vertex set S is k-star-forming if and only if every vertex v outside S has at least k neighbours in S, or has a neighbour u in S with at least k − 1 neighbours in S.
Statement
theorem simple_graph_is_k_star_forming_iff {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 1 ≤ k) (S : Finset V) : simple_graph_is_k_star_forming G k S ↔ ∀ v, v ∉ S → k ≤ (S.filter (G.Adj v)).card ∨ ∃ u ∈ S, G.Adj v u ∧ k - 1 ≤ (S.filter (G.Adj u)).card
- Formalizes
- arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Lemma 2.2.
- 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 4
- 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).
- simple_graph_k_independence_number_le_upper_k_star_forming_numberFor every finite graph G and every k, β_k(G) ≤ SF_k(G).
- 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}.
- chain_graph_two_independence_number_eq_upper_two_star_forming_numberFor every finite chain graph G, the dissociation number β₂(G) equals the upper 2-star-forming number SF₂(G).
The proof, explained
The equivalence is proved by case analysis in both directions. If $S$ is $k$-star-forming, any vertex $v \notin S$ is either the center or a leaf of a $k$-star whose vertices lie in $S \cup \{v\}$; irreflexivity of the graph forces all leaves to lie in $S$ when $v$ is the center (yielding $k$ neighbours), or forces the center to lie in $S$ with $k - 1$ other leaves in $S$ when $v$ is a leaf. Conversely, $k$ neighbours of $v$ in $S$ form the leaves of a star centered at $v$, while a neighbour $u \in S$ with $k - 1$ neighbours in $S$ serves as the center of a star whose leaves are $v$ together with those $k - 1$ neighbours.
To establish the forward direction, consider any $v \notin S$ and distinguish whether $v$ is the center or a leaf of the witnessing $k$-star.
We split the bi-implication using `constructor`. Assuming $S$ is $k$-star-forming and taking $v \notin S$, the definition provides a star with center $c$ and leaf set $L$ of size $k$ such that all vertices lie in $S \cup \{v\}$, $c$ is adjacent to each leaf, and $v = c$ or $v \in L$. We split into these two cases.
constructor · intro h v hv obtain ⟨c, L, hc, hL, hcard, hadj, hvc⟩ := h v hv rcases hvc with rfl | hvL
If $v$ is the center of the star, then $v$ has at least $k$ neighbours in $S$.
When $v = c$, the center is $v$ and the leaf set $L$ has cardinality $k$. Because simple graphs have no self-loops (`G.irrefl`), no leaf in $L$ can equal $v$. Since every leaf is in $S \cup \{v\}$, all leaves must belong to $S$. Thus $L$ is a subset of the neighbours of $v$ in $S$ (`mem_filter`), which by monotonicity of cardinality (`card_le_card`) implies that $v$ has at least $|L| = k$ neighbours in $S$.
uses
card_le_card,mem_filter,G.irrefl· left rw [← hcard] apply card_le_card intro x hx rw [mem_filter] rcases hL x hx with rfl | hxS · exact absurd (hadj _ hx) G.irrefl · exact ⟨hxS, hadj x hx⟩
If $v$ is a leaf of the star, then $v$ has a neighbour $c \in S$ with at least $k - 1$ neighbours in $S$.
When $v \in L$, the center $c$ is adjacent to $v$. By irreflexivity (`G.irrefl`), $c \ne v$, and since $c \in S \cup \{v\}$, this forces $c \in S$. Removing $v$ from $L$ leaves a set $L \setminus \{v\}$ of size $k - 1$ (`card_erase_of_mem`). Every $x \in L \setminus \{v\}$ is adjacent to $c$, and since $x \ne v$ (`mem_erase`) and $x \in S \cup \{v\}$, every such $x$ lies in $S$. Hence $L \setminus \{v\}$ is a subset of the neighbours of $c$ in $S$ (`mem_filter`), so $c$ has at least $k - 1$ neighbours in $S$ by cardinality monotonicity (`card_le_card`).
uses
G.irrefl,card_erase_of_mem,card_le_card,mem_erase,mem_filter· right have hcv : c ≠ v := fun h => G.irrefl (by have := hadj v hvL; rwa [← h] at this) have hcS : c ∈ S := hc.resolve_left hcv refine ⟨c, hcS, (hadj v hvL).symm, ?_⟩ have : (L.erase v).card = k - 1 := by rw [card_erase_of_mem hvL, hcard] rw [← this] apply card_le_card intro x hx rw [mem_erase] at hx rw [mem_filter] exact ⟨(hL x hx.2).resolve_left hx.1, hadj x hx.2⟩
In the reverse direction, if $v \notin S$ has at least $k$ neighbours in $S$, then a $k$-star centered at $v$ witnesses the star-forming property.
Assuming the disjunction holds and taking $v \notin S$, we first consider the case where $v$ has at least $k$ neighbours in $S$. We pick a subset $L \subseteq S \cap N(v)$ of size $k$ (`exists_subset_card_eq`). Choosing $v$ as the center and $L$ as the leaf set satisfies all required conditions: the center is $v$, every leaf is in $S$, $|L| = k$, $v$ is adjacent to every leaf, and $v$ is the center.
uses
exists_subset_card_eq· intro h v hv rcases h v hv with h1 | ⟨u, huS, hvu, h2⟩ · obtain ⟨L, hLs, hLc⟩ := exists_subset_card_eq h1 refine ⟨v, L, Or.inl rfl, fun x hx => Or.inr (mem_filter.1 (hLs hx)).1, hLc, fun x hx => (mem_filter.1 (hLs hx)).2, Or.inl rfl⟩
In the reverse direction, if $v \notin S$ has a neighbour $u \in S$ with at least $k - 1$ neighbours in $S$, then a $k$-star centered at $u$ witnesses the star-forming property.
In the second case, $v$ has a neighbour $u \in S$ with at least $k - 1$ neighbours in $S$. We pick a subset $L \subseteq S \cap N(u)$ of size $k - 1$ (`exists_subset_card_eq`). Since $L \subseteq S$ and $v \notin S$, $v \notin L$. We choose $u$ as the center and $\{v\} \cup L$ as the leaf set (`mem_insert_self`). All leaves belong to $S \cup \{v\}$, $u$ is adjacent to $v$ and to all elements of $L$, and the number of leaves is $(k - 1) + 1 = k$ (`card_insert_of_notMem`), using $k \ge 1$ via linear arithmetic (`omega`). Thus this star witnesses star-formation for $v$.
uses
exists_subset_card_eq,mem_insert_self,card_insert_of_notMem· obtain ⟨L, hLs, hLc⟩ := exists_subset_card_eq h2 have hvL : v ∉ L := fun h => hv (mem_filter.1 (hLs h)).1 refine ⟨u, insert v L, Or.inr huS, ?_, ?_, ?_, Or.inr (mem_insert_self v L)⟩ · intro x hx rcases mem_insert.1 hx with rfl | hx · exact Or.inl rfl · exact Or.inr (mem_filter.1 (hLs hx)).1 · rw [card_insert_of_notMem hvL, hLc] omega · intro x hx rcases mem_insert.1 hx with rfl | hx · exact hvu.symm · exact (mem_filter.1 (hLs hx)).2
card_le_card- If $s \subseteq t$ for finite sets $s$ and $t$, then $|s| \le |t|$.
mem_filter- An element $a$ belongs to the sub-finset of $s$ filtered by predicate $p$ if and only if $a \in s$ and $p(a)$ holds.
G.irrefl- In a simple graph $G$, no vertex is adjacent to itself (adjacency is irreflexive).
card_erase_of_mem- If an element $a$ belongs to a finite set $s$, then the cardinality of $s \setminus \{a\}$ is $|s| - 1$.
mem_erase- An element $a$ belongs to $s \setminus \{b\}$ if and only if $a \ne b$ and $a \in s$.
exists_subset_card_eq- If a finite set $s$ satisfies $n \le |s|$, then there exists a subset $t \subseteq s$ with $|t| = n$.
mem_insert_self- The element $a$ is an element of the set $\{a\} \cup s$ obtained by inserting $a$ into $s$.
card_insert_of_notMem- If $a \notin s$ for a finite set $s$, then $|\{a\} \cup s| = |s| + 1$.
- The arithmetic equality $(k - 1) + 1 = k$ for $k \ge 1$ in the second construction is solved automatically by linear arithmetic (`omega`).
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_iff {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (hk : 1 ≤ k) (S : Finset V) : simple_graph_is_k_star_forming G k S ↔ ∀ v, v ∉ S → k ≤ (S.filter (G.Adj v)).card ∨ ∃ u ∈ S, G.Adj v u ∧ k - 1 ≤ (S.filter (G.Adj u)).card := open Finset in by constructor · intro h v hv obtain ⟨c, L, hc, hL, hcard, hadj, hvc⟩ := h v hv rcases hvc with rfl | hvL · left rw [← hcard] apply card_le_card intro x hx rw [mem_filter] rcases hL x hx with rfl | hxS · exact absurd (hadj _ hx) G.irrefl · exact ⟨hxS, hadj x hx⟩ · right have hcv : c ≠ v := fun h => G.irrefl (by have := hadj v hvL; rwa [← h] at this) have hcS : c ∈ S := hc.resolve_left hcv refine ⟨c, hcS, (hadj v hvL).symm, ?_⟩ have : (L.erase v).card = k - 1 := by rw [card_erase_of_mem hvL, hcard] rw [← this] apply card_le_card intro x hx rw [mem_erase] at hx rw [mem_filter] exact ⟨(hL x hx.2).resolve_left hx.1, hadj x hx.2⟩ · intro h v hv rcases h v hv with h1 | ⟨u, huS, hvu, h2⟩ · obtain ⟨L, hLs, hLc⟩ := exists_subset_card_eq h1 refine ⟨v, L, Or.inl rfl, fun x hx => Or.inr (mem_filter.1 (hLs hx)).1, hLc, fun x hx => (mem_filter.1 (hLs hx)).2, Or.inl rfl⟩ · obtain ⟨L, hLs, hLc⟩ := exists_subset_card_eq h2 have hvL : v ∉ L := fun h => hv (mem_filter.1 (hLs h)).1 refine ⟨u, insert v L, Or.inr huS, ?_, ?_, ?_, Or.inr (mem_insert_self v L)⟩ · intro x hx rcases mem_insert.1 hx with rfl | hx · exact Or.inl rfl · exact Or.inr (mem_filter.1 (hLs hx)).1 · rw [card_insert_of_notMem hvL, hLc] omega · intro x hx rcases mem_insert.1 hx with rfl | hx · exact hvu.symm · exact (mem_filter.1 (hLs hx)).2