simple_graph_is_degenerate
def
A 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 cardinality of the set of neighbors of v lying in s is at most k.
Statement
def simple_graph_is_degenerate {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
- Defined in
- arXiv:2611.04674, Section 1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 5
- simple_graph_is_degenerate_of_induce_compl_singletonIf 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.
- tree_edge_disjoint_embedding_of_star_TFor n ≥ 2, if T is a spanning star tree on Fin n with center r, then every tree S on Fin (n - 1) can be embedded into Fin n…
- simple_graph_is_degenerate_botThe empty graph on any vertex type V is k-degenerate for every natural number k.
- simple_graph_is_degenerate_of_leIf a simple graph G is a subgraph of G' (meaning G ≤ G') and G' is k-degenerate, then G is also k-degenerate.
- tree_edge_disjoint_embedding_two_degenerate_union_twoFor n = 2, any tree S on Fin 1 can be embedded into Fin 2 edge-disjointly from a spanning tree T on Fin 2 such that the union graph T ⊔…
Read back from the Lean
Given a type V, a simple graph G on V, and a natural number k, simple_graph_is_degenerate G k asserts that 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 that lie in s (i.e., s ∩ G.neighborSet v) 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.
Lean source view module on GitHub
/-- A simple graph is k-degenerate if every nonempty subset of vertices contains a vertex with at most k neighbors in the subset. -/ def simple_graph_is_degenerate {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := ∀ s : Set V, s.Nonempty → ∃ v ∈ s, (s ∩ G.neighborSet v).encard ≤ k