AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_like_deletion_number_eq_zero_of_star_like

theoremverified

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

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.

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

    lines 5–8

    uses Finset.coe_inj.mp, Set.coe_toFinset

      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]
  2. 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.

    lines 17–19

    uses SimpleGraph.degree_induce_of_neighborSet_subset, simple_graph_star_like_deletion_number_eq_zero_of_star_like_deg_irrel

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

    lines 27–46

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

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

    lines 52–56

    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_induce

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

    lines 60–64

    uses Nat.sInf_eq_zero.mpr, Or.inl, simple_graph_star_like_deletion_number_eq_zero_of_star_like_star_like_induce

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

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

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