r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal)

Statement

A graph $G$ is $r$-degenerate if *every* subgraph of $G$ (equivalently, every induced subgraph) has a vertex of degree $\le r$. The degeneracy of $G$, $\deg^*(G)$, is the least such $r$.

Formally: $G$ is $r$-degenerate $\iff$ $\max_{H \subseteq G} \min_{v \in H} \deg_H(v) \le r$, where the max ranges over all (induced) subgraphs $H$ of $G$.

Three standard equivalent characterizations (en.wikipedia.org/wiki/Degeneracy_(graph_theory)):

1. Elimination ordering / coloring number (Erdős–Hajnal): $G$ is $r$-degenerate iff its vertices admit a linear ordering $v_1,\dots,v_n$ such that every $v_i$ has at most $r$ neighbors among $v_1,\dots,v_{i-1}$ ("back-degree" $\le r$). The coloring number $\mathrm{col}(G)$ is the least $\kappa$ such that such an ordering exists with back-degree $<\kappa$; degeneracy $= \mathrm{col}(G) - 1$. 2. $k$-core / peeling process: repeatedly delete any vertex of current degree $\le r$ until the graph is empty; this succeeds (empties the graph) iff $G$ is $r$-degenerate. The degeneracy equals the largest $k$ for which $G$ has a nonempty $k$-core (a maximal subgraph with all degrees $\ge k$), and the elimination order above is exactly the reverse of a valid peeling order. 3. DAG orientation: $G$ is $r$-degenerate iff its edges can be oriented to form a DAG (acyclic orientation) with every vertex's out-degree $\le r$.

Facts

- Origin / naming: the "coloring number" formulation is due to Erdős and Hajnal; the "$k$-degenerate" terminology and the subgraph-minimum-degree definition is due to Lick and White, "$k$-Degenerate Graphs," *Canad. J. Math.* (1970) (en.wikipedia.org/wiki/Degeneracy_(graph_theory), cambridge.org/core listing). The bound relating degeneracy to chromatic number is the Szekeres–Wilf theorem (1968): $\chi(G) \le 1 + \max_{H\subseteq G}\delta(H)$, i.e. an $r$-degenerate graph is always $(r{+}1)$-colorable, via the trivial greedy algorithm along the elimination order (fact 1 above): color vertices in order $v_1,\dots,v_n$; each $v_i$ has $\le r$ already-colored neighbors, so a palette of $r+1$ colors always has one free. - Linear-time computation: Matula & Beck (1983) give an $O(|V|+|E|)$ algorithm — bucket vertices by current degree, repeatedly pop and remove a minimum-degree vertex, updating buckets — that computes the degeneracy and a valid elimination order simultaneously (en.wikipedia.org/wiki/Degeneracy_(graph_theory)). - Canonical examples: forests are $1$-degenerate; planar graphs have degeneracy $\le 5$ (via Euler's formula, every planar graph has a vertex of degree $\le 5$, and this is hereditary to subgraphs since planarity is hereditary); outerplanar graphs have degeneracy $\le 2$; a graph with $O(1)$-bounded average degree in every subgraph (e.g. graphs excluding a fixed minor, by the Kostochka/Thomason bound) has $O(\sqrt{\log h})\cdot h$ or $O(h\sqrt{\log h})$ degeneracy when excluding $K_h$; Barabási–Albert preferential-attachment graphs with parameter $m$ are $m$-degenerate by construction (each new vertex arrives with exactly $m$ edges to earlier vertices) (en.wikipedia.org/wiki/Degeneracy_(graph_theory)). - Relation to arboricity: degeneracy is within a constant factor of the arboricity $a(G)$ (min number of forests covering $E(G)$): $a(G) \le \deg^*(G) \le 2a(G) - 1$ roughly (both are sparsity measures controlled by the densest-subgraph edge/vertex ratio, via the Nash-Williams formula for arboricity). - Relation to treewidth: $\deg^*(G) \le \mathrm{tw}(G)$ always (a tree-decomposition elimination order is also a degeneracy-bounding order), so bounded-treewidth graph classes are automatically bounded-degeneracy, but not conversely (e.g. bounded-degree expanders have $O(1)$ degeneracy but unbounded treewidth). - Clique counting: an $n$-vertex $d$-degenerate graph has at most $(n-d)3^{d/3}$ maximal cliques (when $d \equiv 0 \bmod 3$) — the degeneracy elimination order directly bounds the search space for maximal-clique enumeration (en.wikipedia.org/wiki/Degeneracy_(graph_theory)). - Ramsey numbers of degenerate graphs — Burr–Erdős conjecture, proved by Lee (2017): for every $d$ there is $c(d)$ such that every $n$-vertex graph $H$ with degeneracy $\le d$ has Ramsey number $r(H,H) \le c(d)\, n$ — i.e. bounded degeneracy alone (far weaker than bounded max-degree) forces *linear* Ramsey growth. Proved by Choongbum Lee, "Ramsey numbers of degenerate graphs," *Ann. of Math.* 185(3) (2017), 791–829 (gilkalai.wordpress.com/2015/05/22, gil-kalai summary of Lee's proof announcement). - Erdős–Simonovits bipartite-Turán program (the main open-problem cluster using $r$-degeneracy): Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ conjectures that every bipartite $r$-degenerate $H$ satisfies $\mathrm{ex}(n;H) = O(n^{2-1/r})$ — still OPEN even for $r=2$ as of 2026-07-02 (verified in problems/146.md). The best known *fully general* bound is Alon–Krivelevich–Sudakov's $O(n^{2-1/(4r)})$ (2003); the *sharp* $O(n^{2-1/r})$ exponent is proved only for structured sub-families: one-sided-bounded-degree $H$ (Füredi 1991 / AKS 2003), $r$-degenerate blow-ups of trees (Grzesik–Janzer–Nagy, arXiv:1904.07219, 2019), and the larger "tree-degenerate" class (Jiang–Longbrake, arXiv:2201.10699, 2022, via nested dependent random choice) — see Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022) for the full technique writeup. The *companion* conjectures Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 (the $r=2$ "iff", not just "if") and Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ (a converse lower-bound direction) were both disproved by Oliver Janzer (arXiv:2109.06110), showing low Turán exponent does *not* imply low degeneracy — the disproof direction is different from #146's own (still-open) direction.

Technique

When it applies: $r$-degeneracy is the right hypothesis whenever a proof needs "locally sparse everywhere, not just on average" — i.e. a guarantee that survives taking *any* subgraph, not merely one that holds for $G$ itself. This is strictly stronger than bounding average degree (a graph can have low average degree overall while containing a dense clique as a subgraph — that clique would violate $r$-degeneracy for any $r$ less than its size minus one) and strictly weaker than bounding maximum degree (a star $K_{1,n}$ is $1$-degenerate despite unbounded max degree). It is the natural hypothesis for: - Greedy/inductive coloring or embedding arguments — the elimination order lets you process vertices one at a time, each time facing only $\le r$ "already committed" neighbors, so any argument of the form "handle $v$ given its $\le r$ earlier-neighbors' state" goes through by induction on the order (this is literally the Szekeres–Wilf $(r{+}1)$-coloring proof, and the template behind bounded-degeneracy list-coloring/choosability bounds). - Turán-type extremal bounds for sparse target graphs (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ cluster) — degeneracy is exactly the parameter controlling the Kővári–Sós–Turán-style counting: an $r$-degenerate $H$ can be built up one vertex at a time with each new vertex needing only $r$ common neighbors among previously-placed vertices, which is what dependent-random-choice / supersaturation embedding arguments exploit (the "$\le r$ back-degree" ordering is literally the greedy embedding order). - Ramsey-number linearity for sparse graphs (Burr–Erdős/Lee) — bounded degeneracy, not bounded max-degree, turns out to be the *sharp* sparsity notion for forcing linear-in-$n$ Ramsey numbers, because the embedding arguments (again dependent random choice) only ever need to control back-degree along an elimination order, never full degree. - Recursive/hereditary structural bounds (planarity, bounded-genus, minor-closed families) — any class closed under taking subgraphs and satisfying a linear edge bound $|E(H)|\le c|V(H)|$ for all $H$ in the class is automatically $2c$-degenerate (average degree $\le 2c$ in every subgraph forces *some* vertex of degree $\le 2c$ in every subgraph, by a simple counting/pigeonhole argument), which is how planarity ($|E|\le 3|V|-6$) yields degeneracy $\le 5$.

Why it works (the mechanism): the defining property is hereditary (closed under taking subgraphs) and self-witnessing via an ordering: if every subgraph has a low-degree vertex, you can always peel one off, recurse on the remainder (still $r$-degenerate, since it's a subgraph), and get a full elimination order for free (fact 2, the $k$-core peeling process). This ordering is the single object that converts a *global* structural hypothesis ("bounded in every subgraph") into a *local, sequential* one ("bounded back-degree along this specific order") that induction, greedy algorithms, and probabilistic embedding arguments can consume one step at a time — this is the recombination hook: whenever a proof needs to build/color/embed an object vertex-by-vertex while only ever paying a bounded "cost" per step for interactions with what's already placed, check whether the relevant structure is $r$-degenerate first, because the elimination order is handed to you for free by the hypothesis.

How to actually use it to prove something (recipe): 1. Confirm/derive the elimination order: peel minimum-degree vertices (Matula–Beck, linear time) to certify $G$ (or your target graph $H$) is $r$-degenerate and produce the order $v_1,\dots,v_n$ with back-degree $\le r$. 2. Design the inductive/greedy step to only ever need information about a vertex's $\le r$ back-neighbors (coloring: $r+1$ colors always leave one free; embedding: only need $\le r$ common-neighborhood conditions to extend a partial embedding). 3. For extremal/Turán-style bounds, feed the ordering into a dependent-random-choice or supersaturation argument: because each new vertex of $H$ needs only $r$ pre-existing common neighbors to attach to, a host graph with enough edges will (whp) contain a large enough "dense-common-neighborhood" set at every step, by union-bound/concentration over the $r$-wise codegree. 4. For coloring-type or Ramsey-type conclusions, chain the per-step guarantee ($r+1$ colors suffice; embed with room to spare) across the whole order via induction, exactly as in the Szekeres–Wilf argument.

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the general Erdős–Simonovits conjecture ($500, still OPEN even at $r=2$): bipartite $r$-degenerate $H \Rightarrow \mathrm{ex}(n;H)=O(n^{2-1/r})$; $r$-degeneracy is the structural hypothesis the entire conjecture is built on. - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — the $r=2$ "iff" companion conjecture, disproved (Janzer, arXiv:2109.06110): low Turán exponent does not require 2-degeneracy. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — the converse lower-bound companion conjecture, disproved for $r\ge3$ (Janzer). - Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022) — the largest currently-solved sub-territory of erdos/146 (tree-degenerate graphs), via nested dependent random choice; the direct worked example of this concept's Turán-side technique in action. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the workhorse embedding technique that consumes an $r$-degeneracy elimination order to prove Turán/Ramsey bounds for sparse target graphs. - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — $\mathrm{ex}(n;H)$, the extremal quantity the whole Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ cluster is about; degeneracy is the structural parameter controlling the conjectured exponent. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — combined with degeneracy-order embedding in Grzesik–Janzer–Nagy's tree-blow-up proof (arXiv:1904.07219). - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — Kővári–Sós–Turán, the base-case counting bound that one-sided-bounded-degree (a strong form of degeneracy) reduces to. - Random algebraic construction (Bukh; Bukh–Conlon) — random low-degree polynomials over $\\mathbb F_q$ for Turán lower bounds — the lower-bound/counterexample toolkit (Janzer, Bukh–Conlon) used against degeneracy-based conjectures in this cluster.