AFTD Auto-Formalizing Theoretical Domains

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

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