Degeneracy (graph theory)

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has at least one vertex of degree at most ${\displaystyle k}$. That is, some vertex in the subgraph touches ${\displaystyle k}$ or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of ${\displaystyle k}$ for which it is ${\displaystyle 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.

Degeneracy is also known as the k-core number, width, and linkage, and is essentially the same as the coloring number or Szekeres–Wilf number (named after Szekeres and Wilf (1968)). The ${\displaystyle k}$-degenerate graphs have also been called k-inductive graphs. The degeneracy of a graph may be computed in linear time by an algorithm that repeatedly removes minimum-degree vertices. The connected components that are left after all vertices of degree less than ${\displaystyle k}$ have been (repeatedly) removed are called the k-cores of the graph and the degeneracy of a graph is the largest value ${\displaystyle k}$ such that it has a ${\displaystyle k}$-core.