K-core

k-Cores

A ${\displaystyle k}$-core of a graph ${\displaystyle G}$ is a maximal connected subgraph of ${\displaystyle G}$ in which all vertices have degree at least ${\displaystyle k}$. Equivalently, it is one of the connected components of the subgraph of ${\displaystyle G}$ formed by repeatedly deleting all vertices of degree less than ${\displaystyle k}$. If a non-empty ${\displaystyle k}$-core exists, then, clearly, ${\displaystyle G}$ has degeneracy at least ${\displaystyle k}$, and the degeneracy of ${\displaystyle G}$ is the largest ${\displaystyle k}$ for which ${\displaystyle G}$ has a ${\displaystyle k}$-core.