simple_graph_star_like_deletion_number_eq_zero_of_star_like
If a finite simple graph G is star-like, its star-like deletion number d_*(G) is zero.
Statement
theorem simple_graph_star_like_deletion_number_eq_zero_of_star_like {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hstar : simple_graph_is_star_like G) : simple_graph_star_like_deletion_number G = 0
- Source
- step towards dominating_average_star_like_vertex_stability
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_star_like_deletion_numberThe star-like deletion number d_*(G) of a finite simple graph G is the minimum cardinality of a subset X of vertices such that the induced…
- simple_graph_is_star_likeG is star-like: every vertex is either a leaf (degree one) or an l-stem with 1 ≤ l ≤ 2.
- simple_graph_leaf_neighbor_countThe number of leaf neighbours (neighbours of degree one) of a vertex v; v is an l-stem when this number is l ≥ 1.
The proof, explained
The star-like deletion number $d_*(G)$ is defined as the minimum size of a vertex subset $X$ whose deletion leaves an induced subgraph $G[V \setminus X]$ that is star-like. To show that $d_*(G) = 0$ for a star-like graph $G$, it suffices to exhibit a valid deletion set of size zero, namely the empty set $X = \emptyset$. The induced subgraph on $V \setminus \emptyset = V$ inherits the vertex degrees and leaf-neighbor counts of $G$, and therefore remains star-like. Since $0$ belongs to the set of valid deletion sizes, its infimum $d_*(G)$ is zero.
The degree of a vertex does not depend on the choice of finite type instance on its neighbor set.
The degree of a vertex $v$ is defined as the cardinality of its neighbor set converted to a finite set (`Finset.card`). Two finite set representations of the same underlying set are identical because coercing both to sets yields the same neighbor set (`Set.coe_toFinset`), and coercion to sets is injective (`Finset.coe_inj.mp`). Rewriting by this equality shows the cardinalities are equal.
uses
Finset.coe_inj.mp,Set.coe_toFinsetshow @Finset.card V (@Set.toFinset V (G.neighborSet v) i₁) = @Finset.card V (@Set.toFinset V (G.neighborSet v) i₂) have h : @Set.toFinset V (G.neighborSet v) i₁ = @Set.toFinset V (G.neighborSet v) i₂ := Finset.coe_inj.mp (by rw [Set.coe_toFinset, Set.coe_toFinset]) rw [h]
If a vertex subset $s$ contains all vertices of $G$, the degree of any vertex in the induced subgraph $G[s]$ equals its degree in $G$.
Because every vertex of $G$ lies in $s$, the neighbor set in $G$ of any vertex $u \in s$ is contained in $s$. Mathlib's lemma `SimpleGraph.degree_induce_of_neighborSet_subset` then shows that the induced degree equals the original degree for canonical instances. Using transitivity and instance irrelevance (`simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel`), the equality holds for any choice of finite type instances.
uses
SimpleGraph.degree_induce_of_neighborSet_subset,simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrelhave h := SimpleGraph.degree_induce_of_neighborSet_subset (G := G) (s := s) (v := u) (fun x _ => hs x) exact (simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel _ u i _).trans (h.trans (simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel _ _ _ j))
If a vertex subset $s$ contains all vertices of $G$, the number of leaf neighbors of any vertex in $G[s]$ equals its leaf-neighbor count in $G$.
Unfolding the definition of `simple_graph_leaf_neighbor_count`, the count is the cardinality of the finset of adjacent vertices having degree 1. We establish that this cardinality is preserved using a bijection given by the subtype coercion $u \mapsto \uparrow u$ (`Finset.card_bij`): 1. Target membership: If $u$ is adjacent to $w$ in $G[s]$ and has degree 1 in $G[s]$, then $\uparrow u$ is adjacent to $\uparrow w$ in $G$ (`SimpleGraph.induce_adj.mp`) and has degree 1 in $G$ by degree transfer (`simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer`). 2. Injectivity: Coercion from a subtype is injective (`Subtype.ext`). 3. Surjectivity: If $b$ is a leaf neighbor of $\uparrow w$ in $G$, then since $s$ contains all vertices ($hs$), $b$ lifts to $\langle b, hs(b) \rangle \in s$, which is adjacent to $w$ in $G[s]$ (`SimpleGraph.induce_adj.mpr`) with induced degree 1 by degree transfer.
uses
Finset.card_bij,Finset.mem_filter,SimpleGraph.mem_neighborFinset,SimpleGraph.induce_adj.mp,simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer,Subtype.ext,SimpleGraph.induce_adj.mprsimp only [simple_graph_leaf_neighbor_count] refine Finset.card_bij (fun u _ => (↑u : V)) ?_ ?_ ?_ · intro u hu rw [Finset.mem_filter] at hu ⊢ refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset] at hu ⊢ exact SimpleGraph.induce_adj.mp hu.1 · exact (simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer (G := G) hs u _ _).symm.trans hu.2 · intro u₁ _ u₂ _ h exact Subtype.ext h · intro b hb rw [Finset.mem_filter] at hb refine ⟨⟨b, hs b⟩, ?_, rfl⟩ rw [Finset.mem_filter] refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset] rw [SimpleGraph.mem_neighborFinset] at hb exact SimpleGraph.induce_adj.mpr hb.1 · exact (simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer (G := G) hs ⟨b, hs b⟩ _ _).trans hb.2
If $G$ is star-like and $s$ contains all vertices of $G$, then the induced subgraph $G[s]$ is star-like.
By definition, a graph is star-like if every vertex either has degree 1 or between 1 and 2 leaf neighbors. For any vertex $w \in s$, the star-likeness hypothesis for $G$ holds at $\uparrow w \in V$. Rewriting the degree of $w$ in $G[s]$ to the degree of $\uparrow w$ in $G$ using `simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer`, and rewriting the leaf-neighbor count using `simple_graph_star_like_deletion_number_eq_zero_of_star_like_leaf_count_induce`, the star-likeness condition for $w$ in $G[s]$ matches the condition for $\uparrow w$ in $G$.
uses
simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer,simple_graph_star_like_deletion_number_eq_zero_of_star_like_leaf_count_induceintro w have hw := hstar (↑w : V) rw [simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer (G := G) hs w _ _, simple_graph_star_like_deletion_number_eq_zero_of_star_like_leaf_count_induce (G := G) hs w] exact hw
The star-like deletion number $d_*(G)$ is zero.
Unfolding `simple_graph_star_like_deletion_number`, it is defined as the infimum of sizes $|X|$ of vertex subsets $X$ such that the induced subgraph $G[X^c]$ is star-like. To prove the infimum is zero, it suffices by `Nat.sInf_eq_zero.mpr` (via `Or.inl`) to show that $0$ belongs to this set. We take $X = \emptyset$, which has $|X| = 0$. Its complement $X^c = \emptyset^c = V$ contains every vertex ($v \in \emptyset^c$, closed by `simp`). Applying `simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induce` to $s = \emptyset^c$ shows that $G[\emptyset^c]$ is star-like, which witnesses that $0$ is in the set.
uses
Nat.sInf_eq_zero.mpr,Or.inl,simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induceunfold simple_graph_star_like_deletion_number refine Nat.sInf_eq_zero.mpr (Or.inl ?_) refine ⟨∅, ?_, rfl⟩ exact simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induce (G := G) (s := ((↑(∅ : Finset V)) : Set V)ᶜ) (fun v => by simp) hstar
Finset.coe_inj.mp- Two finite sets are equal if their coercions to sets are equal.
Set.coe_toFinset- Coercing a finset back to a set recovers the original set.
SimpleGraph.degree_induce_of_neighborSet_subset- If the neighbor set of a vertex in $G$ is contained in $s$, its degree in the induced subgraph $G[s]$ equals its degree in $G$.
simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel- The degree of a vertex does not depend on the choice of finite type instance on its neighbor set.
Finset.card_bij- Two finite sets have the same cardinality if there exists a bijection between them.
Finset.mem_filter- An element belongs to the filter of a finset by a predicate if and only if it belongs to the finset and satisfies the predicate.
SimpleGraph.mem_neighborFinset- A vertex belongs to the neighbor finset of $v$ if and only if it is adjacent to $v$.
SimpleGraph.induce_adj.mp- If two vertices are adjacent in an induced subgraph, their underlying vertices are adjacent in the ambient graph.
simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer- If a vertex subset $s$ contains all vertices of $G$, the degree of any vertex in $G[s]$ equals its degree in $G$.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
SimpleGraph.induce_adj.mpr- If two vertices in a subset $s$ are adjacent in the ambient graph, they are adjacent in the induced subgraph $G[s]$.
simple_graph_star_like_deletion_number_eq_zero_of_star_like_leaf_count_induce- If a vertex subset $s$ contains all vertices of $G$, the number of leaf neighbors of any vertex in $G[s]$ equals that in $G$.
Nat.sInf_eq_zero.mpr- The infimum of a set of natural numbers is zero if zero belongs to the set (or if the set is empty).
Or.inl- From a proposition $P$, infers the disjunction $P \lor Q$.
simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induce- If $G$ is star-like and a vertex subset $s$ contains all vertices, then the induced subgraph $G[s]$ is star-like.
- In Lean, an induced subgraph $G[s]$ is formally defined on the subtype of vertices belonging to $s$, so $G[V \setminus \emptyset]$ is a formally distinct graph from $G$. Several auxiliary lemmas are needed to transfer vertex degrees, leaf-neighbor counts, and star-likeness across the subtype inclusion.
- In Lemma 1 (`deg_irrel`), Lean requires verifying that the degree of a vertex does not depend on which `Fintype` instance is chosen to measure the cardinality of its neighbor set.
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.
/-- The value of `G.degree v` does not depend on the chosen `Fintype` instance of the neighbour set. -/private lemma simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel {V : Type*} (G : SimpleGraph V) (v : V) (i₁ i₂ : Fintype ↑(G.neighborSet v)) : @SimpleGraph.degree V G v i₁ = @SimpleGraph.degree V G v i₂ := by show @Finset.card V (@Set.toFinset V (G.neighborSet v) i₁) = @Finset.card V (@Set.toFinset V (G.neighborSet v) i₂) have h : @Set.toFinset V (G.neighborSet v) i₁ = @Set.toFinset V (G.neighborSet v) i₂ := Finset.coe_inj.mp (by rw [Set.coe_toFinset, Set.coe_toFinset]) rw [h]/-- If every vertex lies in `s`, the degree of a vertex in the induced subgraph on `s` equals its degree in `G`. -/private lemma simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {s : Set V} [DecidablePred (· ∈ s)] (hs : ∀ v, v ∈ s) (u : ↥s) (i : Fintype ↑((SimpleGraph.induce s G).neighborSet u)) (j : Fintype ↑(G.neighborSet (↑u : V))) : @SimpleGraph.degree _ (SimpleGraph.induce s G) u i = @SimpleGraph.degree _ G (↑u : V) j := by have h := SimpleGraph.degree_induce_of_neighborSet_subset (G := G) (s := s) (v := u) (fun x _ => hs x) exact (simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel _ u i _).trans (h.trans (simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel _ _ _ j))/-- If every vertex lies in `s`, the number of leaf neighbours of a vertex is the same in the induced subgraph on `s` as in `G`. -/private lemma simple_graph_star_like_deletion_number_eq_zero_of_star_like_leaf_count_induce {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {s : Set V} [DecidablePred (· ∈ s)] (hs : ∀ v, v ∈ s) (w : ↥s) : simple_graph_leaf_neighbor_count (SimpleGraph.induce s G) w = simple_graph_leaf_neighbor_count G (↑w : V) := by simp only [simple_graph_leaf_neighbor_count] refine Finset.card_bij (fun u _ => (↑u : V)) ?_ ?_ ?_ · intro u hu rw [Finset.mem_filter] at hu ⊢ refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset] at hu ⊢ exact SimpleGraph.induce_adj.mp hu.1 · exact (simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer (G := G) hs u _ _).symm.trans hu.2 · intro u₁ _ u₂ _ h exact Subtype.ext h · intro b hb rw [Finset.mem_filter] at hb refine ⟨⟨b, hs b⟩, ?_, rfl⟩ rw [Finset.mem_filter] refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset] rw [SimpleGraph.mem_neighborFinset] at hb exact SimpleGraph.induce_adj.mpr hb.1 · exact (simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer (G := G) hs ⟨b, hs b⟩ _ _).trans hb.2/-- Star-likeness passes to the induced subgraph on any vertex set containing all vertices. -/private lemma simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induce {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {s : Set V} [DecidablePred (· ∈ s)] (hs : ∀ v, v ∈ s) (hstar : simple_graph_is_star_like G) : simple_graph_is_star_like (SimpleGraph.induce s G) := by intro w have hw := hstar (↑w : V) rw [simple_graph_star_like_deletion_number_eq_zero_of_star_like_degree_induce_transfer (G := G) hs w _ _, simple_graph_star_like_deletion_number_eq_zero_of_star_like_leaf_count_induce (G := G) hs w] exact hw/-- If G is star-like, then its star-like deletion number d_*(G) is zero. -/theorem simple_graph_star_like_deletion_number_eq_zero_of_star_like {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hstar : simple_graph_is_star_like G) : simple_graph_star_like_deletion_number G = 0 := by unfold simple_graph_star_like_deletion_number refine Nat.sInf_eq_zero.mpr (Or.inl ?_) refine ⟨∅, ?_, rfl⟩ exact simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induce (G := G) (s := ((↑(∅ : Finset V)) : Set V)ᶜ) (fun v => by simp) hstar