simple_graph_is_degenerate_of_induce_compl_singleton
If a simple graph G has a vertex v with degree at most k, and the induced subgraph on {v}ᶜ is k-degenerate, then G is k-degenerate.
Statement
theorem simple_graph_is_degenerate_of_induce_compl_singleton {V : Type*} (G : SimpleGraph V) (v : V) {k : ℕ} (hdeg : (G.neighborSet v).encard ≤ k) (hind : simple_graph_is_degenerate (G.induce ({v}ᶜ : Set V)) k) : simple_graph_is_degenerate G k
- Source
- step towards tree_edge_disjoint_embedding_two_degenerate_union
- Verified
- 08 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…
The proof, explained
To show that G is k-degenerate, we show that every nonempty subset s ⊆ V contains a vertex with at most k neighbors in s. We split into cases depending on whether v ∈ s. If v ∈ s, then v itself has at most k neighbors in s because its degree in all of G is at most k. If v ∉ s, then s is entirely contained in {v}ᶜ; applying the k-degeneracy of the induced subgraph G[{v}ᶜ] yields a vertex in s with at most k neighbors in the induced subgraph, which directly bounds its degree in G[s].
To prove that G is k-degenerate, it suffices to show that every nonempty vertex subset s ⊆ V contains a vertex with at most k neighbors in s.
By the definition of k-degeneracy, we fix an arbitrary subset s ⊆ V and assume s is nonempty.
intro s hsIf v ∈ s, then v has at most k neighbors in s.
We split into cases on whether v ∈ s. When v ∈ s, the neighbors of v in s form a subset of all neighbors of v in G (`Set.inter_subset_right`), so the cardinality |s ∩ N_G(v)| is bounded by the total degree |N_G(v)| (`Set.encard_le_encard`). Since |N_G(v)| ≤ k by hypothesis, transitivity (`le_trans`) confirms that v satisfies the required bound.
uses
Set.inter_subset_right,Set.encard_le_encard,le_transby_cases hvs : v ∈ s · refine ⟨v, hvs, le_trans (Set.encard_le_encard Set.inter_subset_right) hdeg⟩
When v ∉ s, the subset s corresponds to a nonempty set in the induced subgraph on {v}ᶜ.
Because s is nonempty, it contains some element x. Since v ∉ s, we must have x ≠ v, so x ∈ {v}ᶜ. Thus x represents an element of the subtype {v}ᶜ belonging to the preimage of s under the inclusion map, which is therefore nonempty.
· have hs' : (Subtype.val ⁻¹' s : Set ({v}ᶜ : Set V)).Nonempty := by obtain ⟨x, hx⟩ := hs have hxv : x ≠ v := fun h => hvs (h ▸ hx) exact ⟨⟨x, hxv⟩, hx⟩
There exists a vertex w ∈ s whose degree in the induced subgraph G[{v}ᶜ] restricted to s is at most k, reducing the problem to bounding its degree in G[s].
Applying the assumption `hind` that G[{v}ᶜ] is k-degenerate to the nonempty preimage of s, we obtain a vertex w' in {v}ᶜ belonging to s with at most k neighbors in the induced subgraph. Selecting w = w'.val ∈ s as the candidate vertex, it remains to verify that |s ∩ N_G(w)| ≤ k.
obtain ⟨w', hw's, hw'deg⟩ := hind (Subtype.val ⁻¹' s) hs' refine ⟨w'.val, hw's, ?_⟩
The neighbors of w in s within G are contained in the image of the neighbors of w' in the induced subgraph G[{v}ᶜ].
Let x ∈ s ∩ N_G(w). Rewriting with `Set.mem_inter_iff` and `SimpleGraph.mem_neighborSet`, x is in s and adjacent to w in G. Because x ∈ s and v ∉ s, we have x ≠ v, so x forms a vertex ⟨x, x ≠ v⟩ of {v}ᶜ. In the induced subgraph, this vertex belongs to the preimage of s and is adjacent to w' (using `Set.mem_preimage`, `Set.mem_inter_iff`, and `SimpleGraph.mem_neighborSet`), and its image under the subtype inclusion map is x.
uses
Set.mem_inter_iff,SimpleGraph.mem_neighborSet,Set.mem_preimagehave hsub : s ∩ G.neighborSet w'.val ⊆ Subtype.val '' ((Subtype.val ⁻¹' s) ∩ (G.induce ({v}ᶜ : Set V)).neighborSet w') := by intro x hx simp only [Set.mem_inter_iff, SimpleGraph.mem_neighborSet] at hx have hxv : x ≠ v := fun h => hvs (h ▸ hx.1) refine ⟨⟨x, hxv⟩, ?_, rfl⟩ simp only [Set.mem_inter_iff, Set.mem_preimage, SimpleGraph.mem_neighborSet] exact ⟨hx.1, hx.2⟩
The vertex w has at most k neighbors in s within G, completing the proof.
Because the subtype inclusion map is injective, the image of a subset has the same extended cardinality as the subset itself (`Subtype.val_injective.encard_image`). By the previous inclusion, |s ∩ N_G(w)| is at most the cardinality of the neighborhood of w' in the induced subgraph (`Set.encard_le_encard`), which is at most k by `hw'deg`. Applying transitivity of inequality (`le_trans`) completes the proof.
uses
Subtype.val_injective.encard_image,Set.encard_le_encard,le_transhave himg : (Subtype.val '' ((Subtype.val ⁻¹' s) ∩ (G.induce ({v}ᶜ : Set V)).neighborSet w')).encard = ((Subtype.val ⁻¹' s) ∩ (G.induce ({v}ᶜ : Set V)).neighborSet w').encard := Subtype.val_injective.encard_image _ exact le_trans (Set.encard_le_encard hsub) (himg.le.trans hw'deg)
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Set.encard_le_encard- If a set is a subset of another, its extended cardinality is less than or equal to that of the other (s ⊆ t implies |s| ≤ |t|).
Set.inter_subset_right- The intersection of two sets is a subset of the second set (s ∩ t ⊆ t).
Set.mem_inter_iff- An element belongs to the intersection of two sets if and only if it belongs to both sets.
Set.mem_preimage- An element belongs to the preimage of a set under a function if and only if its image belongs to the set.
SimpleGraph.mem_neighborSet- A vertex w is in the neighbor set of v if and only if v and w are adjacent in the graph.
Subtype.val_injective.encard_image- The image of a subset under the subtype inclusion map has the same extended cardinality as the subset.
- In Lean, the vertex set of the induced subgraph on {v}ᶜ is formalized as a subtype. Thus, relations between subsets, neighborhoods, and cardinalities in G and in the induced subgraph require explicit conversions via preimages and images under the subtype inclusion map `Subtype.val`, which on paper are treated as implicit identifications.
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.
/-- If removing a vertex v of degree at most k from a simple graph G leaves a k-degenerate induced subgraph on {v}ᶜ, then G is k-degenerate. -/theorem simple_graph_is_degenerate_of_induce_compl_singleton {V : Type*} (G : SimpleGraph V) (v : V) {k : ℕ} (hdeg : (G.neighborSet v).encard ≤ k) (hind : simple_graph_is_degenerate (G.induce ({v}ᶜ : Set V)) k) : simple_graph_is_degenerate G k := by intro s hs by_cases hvs : v ∈ s · refine ⟨v, hvs, le_trans (Set.encard_le_encard Set.inter_subset_right) hdeg⟩ · have hs' : (Subtype.val ⁻¹' s : Set ({v}ᶜ : Set V)).Nonempty := by obtain ⟨x, hx⟩ := hs have hxv : x ≠ v := fun h => hvs (h ▸ hx) exact ⟨⟨x, hxv⟩, hx⟩ obtain ⟨w', hw's, hw'deg⟩ := hind (Subtype.val ⁻¹' s) hs' refine ⟨w'.val, hw's, ?_⟩ have hsub : s ∩ G.neighborSet w'.val ⊆ Subtype.val '' ((Subtype.val ⁻¹' s) ∩ (G.induce ({v}ᶜ : Set V)).neighborSet w') := by intro x hx simp only [Set.mem_inter_iff, SimpleGraph.mem_neighborSet] at hx have hxv : x ≠ v := fun h => hvs (h ▸ hx.1) refine ⟨⟨x, hxv⟩, ?_, rfl⟩ simp only [Set.mem_inter_iff, Set.mem_preimage, SimpleGraph.mem_neighborSet] exact ⟨hx.1, hx.2⟩ have himg : (Subtype.val '' ((Subtype.val ⁻¹' s) ∩ (G.induce ({v}ᶜ : Set V)).neighborSet w')).encard = ((Subtype.val ⁻¹' s) ∩ (G.induce ({v}ᶜ : Set V)).neighborSet w').encard := Subtype.val_injective.encard_image _ exact le_trans (Set.encard_le_encard hsub) (himg.le.trans hw'deg)