k-degenerate Graph

graph-theory

Definition

$k$-degenerate Graph

A undirected graph is called 1-degenerate if every subgraph has at least one vertex with a degree of at most $k$.

Example: A $1$-degenerate graph starts with exactly one leaf node and upon removal of a leaf node and it’s incident edges, creates a new leaf node.

Examples:

• Forests are always $1$-degenerate and $1$-degenerate graphs are forests