simple_graph_is_degenerate_bot
The empty graph on any vertex type V is k-degenerate for every natural number k.
Statement
theorem simple_graph_is_degenerate_bot (V : Type*) (k : ℕ) : simple_graph_is_degenerate (⊥ : SimpleGraph V) k
- Source
- folklore
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_is_degenerateA simple graph G on a vertex type V is k-degenerate if for every nonempty subset of vertices s ⊆ V, there exists a vertex v ∈ s such that…
Read back from the Lean
For every type V and every natural number k, the empty graph on V (the simple graph with no edges, ⊥ : SimpleGraph V) is k-degenerate. That is, for every nonempty subset s of V, there exists a vertex v ∈ s such that the extended cardinality of the set of neighbors of v in s is at most k.
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
To show that the empty graph ⊥ is k-degenerate, we check the definition: every nonempty subset of vertices s ⊆ V must contain a vertex with at most k neighbors in s. Given any nonempty set s, we pick an arbitrary vertex v ∈ s. Because the empty graph has no edges, the neighborhood of v is empty, so s ∩ N(v) is empty with cardinality 0 ≤ k.
Given a nonempty set of vertices s ⊆ V, selecting any element v ∈ s reduces the goal to showing that |s ∩ N(v)| ≤ k.
By definition, a graph is k-degenerate if every nonempty vertex subset s contains a vertex v ∈ s whose neighborhood in s has cardinality at most k. We introduce the subset s and the hypothesis that it is nonempty (line 4). From nonemptiness, we extract a vertex v ∈ s (line 5). Supplying v and the fact that v ∈ s as witnesses for the existential quantifier leaves only the degree condition |s ∩ N_⊥(v)| ≤ k to be verified (line 6).
intro s hs obtain ⟨v, hv⟩ := hs refine ⟨v, hv, ?_⟩
The number of neighbors of v in s is at most k. automation
In the empty graph ⊥, no two vertices are adjacent, so the neighbor set of v is empty. Therefore s ∩ N_⊥(v) = ∅, which has cardinality 0. Since 0 ≤ k holds for any natural number k, simplification closes the goal automatically.
simp
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 empty graph on any vertex type is k-degenerate for all k. -/theorem simple_graph_is_degenerate_bot (V : Type*) (k : ℕ) : simple_graph_is_degenerate (⊥ : SimpleGraph V) k := by intro s hs obtain ⟨v, hv⟩ := hs refine ⟨v, hv, ?_⟩ simp