AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_degenerate_of_le

theoremverifiedformalization

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.

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

    lines 4–5

      intro s hs
      obtain ⟨v, hv, hcard⟩ := hG' s hs
  2. 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.

    lines 6–7

    uses le_trans, Set.encard_le_encard, Set.inter_subset_inter_right, SimpleGraph.neighborSet_mono

      refine ⟨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

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