Degeneracy (graph theory)¶

The least k such that every nonempty subgraph has a vertex of degree at most k, equivalently the maximum core number in a graph.

Version: v2 · 2026-09-19 · History
Domain-specific #: 4084
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics

Core Idea¶

Graph degeneracy measures hereditary sparsity by the worst minimum degree encountered over all subgraphs. Repeatedly removing a current minimum-degree vertex yields a degeneracy ordering, exposes nested cores and supports bounded-forward-neighbor algorithms. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

The load-bearing residual is not the broad topic of graph theory. It is The least k such that every nonempty subgraph has a vertex of degree at most k, equivalently the maximum core number in a graph.

How would you explain it like I'm…

The Peel-the-Web Number

Imagine dots joined by strings. Keep taking away the dot with the fewest strings. Degeneracy is the biggest number of strings any dot had at the moment you took it away. A small number means the whole picture, and every piece of it, is not very tangled.

Peel-the-Graph Number

A graph is a set of dots with lines between some of them. Degeneracy measures how crowded with lines a graph is, even in its most crowded part. Here is how to find it: over and over, remove a dot with the fewest lines left, and note how many lines it had right then. The largest of those numbers is the degeneracy. If the degeneracy is k, then any piece of the graph you look at always has some dot with k or fewer lines.

Hereditary Sparsity Measure

In graph theory, the degree of a vertex is the number of edges touching it. A graph has Degeneracy (graph theory) k when k is the smallest number such that every nonempty subgraph has at least one vertex of degree at most k. You can compute it by repeatedly deleting a vertex of current minimum degree and recording the largest degree seen at deletion time. The deletion order is called a degeneracy ordering, and in it each vertex has at most k neighbors that come later. It measures sparsity that is hereditary: a graph with small degeneracy is sparse everywhere, not just on average. It equals the largest "core number", where a k-core is a part of the graph in which every vertex has degree at least k.

The degeneracy of a graph is the least k such that every nonempty subgraph contains a vertex of degree at most k; equivalently, it is the maximum over subgraphs of the minimum degree, and also the maximum core number. A graph is called k-degenerate when this holds. The standard algorithm repeatedly removes a vertex of current minimum degree; the maximum degree observed at removal equals the degeneracy, and the removal sequence is a degeneracy ordering in which every vertex has at most k neighbors later in the order. The same peeling process exposes the nested k-cores, maximal subgraphs of minimum degree at least k. Because each vertex has boundedly many forward neighbors, many algorithms (for example, listing cliques or greedy coloring with at most k+1 colors) run efficiently on low-degeneracy graphs. The measure captures hereditary sparsity: unlike average degree, it is controlled by the densest subgraph. To confirm a value k, you must show both that every subgraph has a vertex of degree at most k and that some subgraph has minimum degree exactly k.

Scope of Application¶

Degeneracy (graph theory) belongs to graph theory and is useful where the analyst can specify a finite undirected graph, induced or arbitrary subgraphs under the chosen convention, vertex degrees, iterative peeling order, k-cores and degeneracy value, then evaluate every nonempty subgraph has a vertex of degree at most k and some subgraph has minimum degree exactly k. The scope is broad within that domain but bounded by the need for every nonempty subgraph has a vertex of degree at most k and some subgraph has minimum degree exactly k. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making every nonempty subgraph has a vertex of degree at most k and some subgraph has minimum degree exactly k the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Degeneracy (graph theory) can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Degeneracy (graph theory). Degeneracy (graph theory) compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: a finite undirected graph, induced or arbitrary subgraphs under the chosen convention, vertex degrees, iterative peeling order, k-cores and degeneracy value. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express every nonempty subgraph has a vertex of degree at most k and some subgraph has minimum degree exactly k independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theory because they reuse a finite undirected graph, induced or arbitrary subgraphs under the chosen convention, vertex degrees, iterative peeling order, k-cores and degeneracy value, Repeatedly removing a current minimum-degree vertex yields a degeneracy ordering, exposes nested cores and supports bounded-forward-neighbor algorithms., and type the carrier, state every parameter and convention in the definition, test that every nonempty subgraph has a vertex of degree at most k and some subgraph has minimum degree exactly k, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Degeneracy (graph theory) Domain-specific

Parents (1) — outgoing typed relations

Degeneracy (graph theory) is a kind of Network Prime

The candidate literally instantiates prime:network; What makes it its own entry: The least k such that every nonempty subgraph has a vertex of degree at most k, equivalently the maximum core number in a graph.

Hierarchy path (1) — routes to 1 parentless root

Degeneracy (graph theory) → is a kind of Network

Neighborhood in Abstraction Space¶

Degeneracy (graph theory) sits in a crowded region of the domain-specific corpus (5^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Classes & Invariants (40 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25