simple_graph_star_like_deletion_number_le_card
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
- 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.
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|.
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.
uses
Nat.sInf_leunfold simple_graph_star_like_deletion_number apply Nat.sInf_le
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.
uses
Finset.univrefine ⟨Finset.univ, ?_, by simp⟩
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.
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.
- In Lean, the fact that the empty graph is star-like is formalized by introducing a hypothetical vertex in the induced subgraph on the complement of all vertices and showing that its membership in the empty set is contradictory, which vacuously satisfies the universal condition defining star-like graphs.
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 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)