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 k {\displaystyle k} . That is, some vertex in the subgraph touches k {\displaystyle k} or fewer of the subgraph's edges.