AFTD Auto-Formalizing Theoretical Domains

simple_graph_star_like_deletion_number_le_card

theoremverified

For every finite simple graph G, deleting all vertices leaves the empty graph, which is star-like, so the star-like deletion number d_*(G) is at most the number of vertices of G.

Statement

theorem simple_graph_star_like_deletion_number_le_card {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    simple_graph_star_like_deletion_number G ≤ Fintype.card V
Source
arXiv:2208.10475v2: The average size of a dominating set in a graph
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

For any finite type $V$ with decidable equality and any simple graph $G$ on $V$ with decidable adjacency, the star-like deletion number of $G$ (simple_graph_star_like_deletion_number G) is less than or equal to the cardinality of $V$ (Fintype.card V).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The star-like deletion number of a graph G is the minimum number of vertices that must be deleted so that the remaining induced subgraph is star-like. Deleting the entire vertex set V leaves the empty graph, which has no vertices and therefore vacuously satisfies the definition of being star-like. Since the set of all vertices has size |V|, this candidate deletion set witnesses that the deletion number is at most |V|.

  1. To show that the star-like deletion number of G is at most |V|, it suffices to show that |V| is the size of some vertex subset whose deletion leaves a star-like subgraph.

    Unfolding the definition of simple_graph_star_like_deletion_number, the deletion number is the infimum of the set of sizes of all vertex subsets X ⊆ V whose complement induces a star-like graph. By Nat.sInf_le, the infimum of a set of natural numbers is bounded above by any element of that set, so it suffices to show that |V| belongs to this set.

    lines 5–6

    uses Nat.sInf_le

      unfold simple_graph_star_like_deletion_number
      apply Nat.sInf_le
  2. Choosing the deletion set to be the set of all vertices, its cardinality is |V|, leaving only the requirement that the resulting empty subgraph is star-like.

    We instantiate the deletion set X with Finset.univ, the set of all vertices in V. Simplification verifies that the cardinality of Finset.univ is indeed Fintype.card V, leaving the remaining goal of proving that the subgraph induced on (Finset.univ)ᶜ is star-like.

    line 7

    uses Finset.univ

      refine ⟨Finset.univ, ?_, by simp⟩
  3. The empty induced subgraph is vacuously star-like.

    A graph is star-like if every vertex is either a leaf or has between 1 and 2 leaf neighbors. We introduce an arbitrary vertex w of the induced subgraph on (Finset.univ)ᶜ. The vertex w carries the hypothesis w.2 that it belongs to the complement of the universal set; simplification shows that no such element exists, and absurd discharges the goal from this contradiction.

    lines 8–9

      intro w
      exact absurd w.2 (by simp)
Nat.sInf_le
For any set of natural numbers s and any element m ∈ s, the infimum of s is at most m.
Finset.univ
The finite set of all elements of a finite type.

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 star-like deletion number of G is at most the total number of vertices |V|. -/theorem simple_graph_star_like_deletion_number_le_card {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    simple_graph_star_like_deletion_number G ≤ Fintype.card V := by  unfold simple_graph_star_like_deletion_number  apply Nat.sInf_le  refine ⟨Finset.univ, ?_, by simp⟩  intro w  exact absurd w.2 (by simp)
See it in the graphDiscuss this resultChallenge it