In graph theory, "degeneracy" is a property of a graph that measures how "sparse" the graph is in terms of its connectivity. Specifically, the degeneracy of a graph is defined as the smallest integer \( k \) such that every subgraph of the graph has avertex of degree at most \( k \).