Degeneracy (graph theory)

Summary

In graph theory, a $\boldsymbol{k}$-degenerate graph is an undirected graph in which every non-empty subgraph has at least one vertex of degree at most $k$. That is, some vertex in the subgraph touches $k$ or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of $k$ for which it is $k$-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.