The degeneracy of a graph 
, also known as the 
-core number, graph width, or graph linkage, is defined as
the smallest integer 
such that each subgraph of 
contains a vertex of degree
at most 
.
Equivalently, the degeneracy of a graph 
is the largest 
for which 
has a k-core.
Graph degeneracy is essentially the same as the coloring number and Szekeres-Wilf number.
-vertex-connected graphs have degeneracy
of at least 
.
(Non-empty) trees and forests have degeneracy 1, (finite) planar graphs have degeneracy at most 5, outerplanar graphs have degeneracy at most 2, and Apollonian networks have degeneracy 3.
The degeneracy of a graph may be computed in linear time by repeatedly removing minimum-degree vertices from a graph.
-Degenerate Graphs." Canad. J. Math. 22,
1082-1096, 1970.