AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_degenerate_of_induce_compl_singleton

theoremverified

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].

  1. 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.

    line 6

      intro s hs
  2. If 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.

    lines 7–8

    uses Set.inter_subset_right, Set.encard_le_encard, le_trans

      by_cases hvs : v ∈ s
      · refine ⟨v, hvs, le_trans (Set.encard_le_encard Set.inter_subset_right) hdeg⟩
  3. 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.

    lines 9–12

      · 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⟩
  4. 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.

    lines 13–14

        obtain ⟨w', hw's, hw'deg⟩ := hind (Subtype.val ⁻¹' s) hs'
        refine ⟨w'.val, hw's, ?_⟩
  5. 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.

    lines 15–22

    uses Set.mem_inter_iff, SimpleGraph.mem_neighborSet, Set.mem_preimage

        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⟩
  6. 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.

    lines 23–26

    uses Subtype.val_injective.encard_image, Set.encard_le_encard, le_trans

        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)
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.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it