simple_graph_is_degenerate_of_le
If a simple graph G is a subgraph of G' (meaning G ≤ G') and G' is k-degenerate, then G is also k-degenerate.
Statement
theorem simple_graph_is_degenerate_of_le {V : Type*} {G G' : SimpleGraph V} (h : G ≤ G') {k : ℕ} (hG' : simple_graph_is_degenerate G' k) : simple_graph_is_degenerate G k
- Formalizes
- arXiv:2611.04674, Section 1
- 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
Let V be a type, and let G and G' be simple graphs on V. If G ≤ G' (that is, every edge of G is an edge of G') and G' is k-degenerate (for a natural number k), then G is also k-degenerate.
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 prove that any subgraph G of a k-degenerate graph G' is also k-degenerate, we test an arbitrary nonempty subset of vertices s. Since G' is k-degenerate, s contains a vertex v with at most k neighbors in s with respect to G'. Because G ≤ G', the neighborhood of v in G is a subset of its neighborhood in G', so v has at most as many neighbors in s under G as under G', satisfying the degeneracy requirement.
For an arbitrary nonempty vertex set s, there is a vertex v ∈ s with at most k neighbors in s with respect to G'
By definition, G is k-degenerate if every nonempty subset of vertices contains a vertex with at most k neighbors in that subset. Given such a nonempty set s, the k-degeneracy of the supergraph G' yields a vertex v ∈ s such that |s ∩ N_{G'}(v)| ≤ k.
intro s hs obtain ⟨v, hv, hcard⟩ := hG' s hs
The vertex v has at most k neighbors in s with respect to G as well, establishing that G is k-degenerate
Because G is a subgraph of G' (h : G ≤ G'), the neighborhood of v in G is contained in its neighborhood in G' (SimpleGraph.neighborSet_mono). Intersecting both sides with s gives s ∩ N_G(v) ⊆ s ∩ N_{G'}(v) (Set.inter_subset_inter_right). By monotonicity of extended cardinality (Set.encard_le_encard) and transitivity of inequality (le_trans), |s ∩ N_G(v)| ≤ |s ∩ N_{G'}(v)| ≤ k, so v witnesses the condition for G.
uses
le_trans,Set.encard_le_encard,Set.inter_subset_inter_right,SimpleGraph.neighborSet_monorefine ⟨v, hv, le_trans (Set.encard_le_encard ?_) hcard⟩ exact Set.inter_subset_inter_right s (SimpleGraph.neighborSet_mono h v)
le_trans- transitivity of an ordering: if a ≤ b and b ≤ c, then a ≤ c
Set.encard_le_encard- if s ⊆ t, then the extended cardinality of s is at most that of t
Set.inter_subset_inter_right- if s ⊆ t, then u ∩ s ⊆ u ∩ t for any set u
SimpleGraph.neighborSet_mono- if G ≤ G', then the neighborhood of any vertex v in G is a subset of its neighborhood in G'
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.
/-- Any subgraph of a k-degenerate graph is k-degenerate. -/theorem simple_graph_is_degenerate_of_le {V : Type*} {G G' : SimpleGraph V} (h : G ≤ G') {k : ℕ} (hG' : simple_graph_is_degenerate G' k) : simple_graph_is_degenerate G k := by intro s hs obtain ⟨v, hv, hcard⟩ := hG' s hs refine ⟨v, hv, le_trans (Set.encard_le_encard ?_) hcard⟩ exact Set.inter_subset_inter_right s (SimpleGraph.neighborSet_mono h v)