Degeneracy (Graph Theory)

In graph theory, a graph is k-degenerate if every non-empty subgraph of it has at least one vertex of degree at most k, meaning some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest such k for which it is k-degenerate, a measure of how sparse the graph is that stays within a constant factor of other sparsity measures such as arboricity. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/