---
tag: VY8MGZDQ2J
kind: concept
name: Degeneracy (graph theory)
aliases: [coloring-number, colouring-number, degenerate-graph, graph-degeneracy, k-core, k-cores, szekeres-wilf-number]
sources:
  - wikipedia: en:27545816@r1368656458
    locator: Degeneracy (graph theory)
    note: adopted
    mention: wikipedia://en/27545816
    sections: [Summary]
same_as:
  wikidata: Q5251771
  wikipedia: Degeneracy (graph theory)
inventory: [BEC29N3RPG]
---

## 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|0KS0KRDV4Y]] 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.