AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_star_forming_iff

theoremverifiedformalization

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

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.

  1. 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.

    lines 5–8

      constructor
      · intro h v hv
        obtain ⟨c, L, hc, hL, hcard, hadj, hvc⟩ := h v hv
        rcases hvc with rfl | hvL
  2. 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$.

    lines 9–16

    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⟩
  3. 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`).

    lines 17–27

    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⟩
  4. 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.

    lines 28–32

    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⟩
  5. 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$.

    lines 33–45

    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$.

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_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
See it in the graphDiscuss this resultChallenge it