---
title: "Degree Sequences and Graphical Sequences"
summary: The handshaking lemma's consequences, Erdős–Gallai and Havel–Hakimi — which one to use when you must build the graph.
difficulty: core
tags: [degree sequence, greedy, existence]
prereq: [foundations/types, proofs/double-count]
see: [trees/counting, special/planar]
---

## Realisability

:::definition label="Terms"
A sequence $d_1 \ge d_2 \ge \dots \ge d_n \ge 0$ is **graphical** if some simple graph has exactly these degrees. `deg(v)` = degree; $\sum_v \deg(v) = 2m$ (handshaking).
:::

:::props title="Immediate necessary conditions (all of them cheap to check)"
- $\sum d_i$ is even (handshaking);
- $d_1 \le n - 1$, and more: $\sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i>k} \min(d_i, k)$ for every $k$ — this *is* the full characterisation (below);
- a vertex of degree $n-1$ and a vertex of degree $0$ cannot coexist (and more generally $d_1 = n - 1 - t$ bounds the number of zeros by $t$);
- if exactly one vertex has odd degree, the sequence is not graphical (the count of odd-degree vertices is always even);
- **tree** version: a sequence of $n$ positive integers is the degree sequence of a tree iff $\sum d_i = 2n - 2$ (construct with Prüfer codes, @trees/counting).
:::

## Erdős–Gallai

:::theorem title="Erdős–Gallai (1960)"
$\sum d_i$ is even and for every $1 \le k \le n$,
$$\sum_{i=1}^{k} d_i \;\le\; k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k).$$
:::

:::idea
The left side is the number of edges *inside* the $k$ highest-degree vertices plus those leaving them. The right side is the maximum possible: at most $k(k-1)$ inside (complete graph), and each remaining vertex $i$ can send at most $\min(d_i, k)$ edges into the set. Equality conditions aside, the point is that the "top $k$" is the worst case — which is why sorting is part of the theorem.
:::

## Havel–Hakimi, the constructive test

:::theorem title="Havel–Hakimi (1955), constructive"
$d$ is graphical iff $d_1 = 0$ (all zero) or, with $d_1 = k > 0$, the sequence obtained by deleting $d_1$ and subtracting 1 from the next $k$ entries (then re-sorting) is graphical.
:::

:::proof
Necessity: in any realisation, the vertex of max degree $k$ has $k$ neighbours; those are at least as "hungry" as the others, so if a realisation exists one exists where it attaches to the $k$ largest — the standard **swap argument**: if $u$ (degree $k$) is adjacent to $w$ but not to $v$, and $\deg(v) \ge \deg(w)$ with $v$ adjacent to some neighbour $x$ of... concretely, if $uw \in E$, $uv \notin E$ and there is $x$ with $xv \in E$, $xu \notin E$, then replacing $uw, xv$ by $uv, xw$ keeps every degree and moves an edge toward $v$. Repeating puts $u$'s neighbours among the $k$ largest. Sufficiency is immediate: attach the vertex to those $k$ entries and realise the rest. ∎
:::

## Implementation

```cpp havel-hakimi.cpp
// builds an adjacency matrix, or reports "not graphical"
bool realise(vector<pair<int,int>> d, vector<vector<int>> &A) {   // d = (deg, vertex)
    priority_queue<pair<int,int>> q;
    for (auto [deg, v] : d) if (deg) q.push({deg, v});
    while (q.size()) {
        vector<pair<int,int>> need;
        int k = q.top().first, u = q.top().second; q.pop();
        if (k > (int)q.size()) return false;
        for (int i = 0; i < k; i++) { need.push_back(q.top()); q.pop(); }
        for (auto [deg, v] : need) { A[u][v] = A[v][u] = 1; if (deg - 1 > 0) q.push({deg - 1, v}); }
    }
    return true;
}
```

## Which test, when

:::note title="Which test, when"
- only need **yes/no**, $n \le 5000$: Erdős–Gallai with a two-pointer/sorted-prefix computation, $O(n)$ after sorting (using the $\min$ split point found by binary search) — or just $O(n^2)$, which is $2.5\times10^7$ and fine,
- need the **graph**: Havel–Hakimi with a heap/insertion into a sorted array, $O(n^2)$ or $O(nm)$, and it produces the edges,
- need it to be **connected**: the clean sufficient condition is $2 \le d_n \le d_1 \le n-1$ and $\sum d_i$ even — then Erdős–Gallai applied to the shifted sequence yields a connected realisation (Anstee's characterisation adds the prefix inequalities $\sum_{i=1}^{k} d_i \ge k(k+1)$ replaced by "$>$ for $k<n$", which is what you actually verify), or, easier to code: run Havel–Hakimi on a forced spanning path first and check the remainder is graphical;
- need a **tree**: sum $= 2n-2$ with all $d_i \ge 1$, construct from the Prüfer sequence,
- need a **directed** realisation of (in,out) pairs: the Ford–Fulkerson bipartite test (source→out-vertices→in-vertices→sink, capacity 1, no self-loops and no parallel arcs ⇒ a matching/flow question, @flow/maxflow).
:::

## Regularity and the two classic traps

:::warning title="Regularity and the two classic traps"
A $k$-regular graph on $n$ vertices exists iff $0 \le k < n$ and $nk$ is even. Trap 1: people add "$n \ge 3$" or "simple" conditions that are unnecessary (the cycle gives 2-regular for all $n \ge 3$; two vertices give 1-regular; $k = n-1$ is $K_n$). Trap 2: the **complement** of a $k$-regular graph is $(n-1-k)$-regular — this one-line trick converts "no $k$-regular with property X" into "no $(n-1-k)$-regular with property ¬X" and settles several olympiad claims about self-complementary graphs (which additionally need $n \equiv 0,1 \pmod 4$ since $\binom n2$ must be even).
:::

## Realisation in a contest statement

:::example title="The graph-realisation problem in a contest statement"
"Given $n$ and the multiset of degrees, count the graphs" — hard (no known closed form; only $n \le 6$-ish by brute force, and #P-complete in general). "Given the degrees, does a graph exist" — the two theorems above. "Given the degrees of a bipartite graph (left $a$, right $b$)" — Gale–Ryser: $\sum a = \sum b$ and $\sum_{i=1}^{k} a_i \le \sum_j \min(b_j, k)$ for all $k$, with the same greedy proof. Know the three variants so a statement never surprises you.
:::

:::problems
- [[CSES 1134]] Prüfer Code | https://cses.fi/problemset/task/1134 | easy | the tree case: degree of $v$ = occurrences of $v$ + 1, exactly why $\sum d_i = 2n-2$
- [[CSES 2138]] Reachable Nodes | https://cses.fi/problemset/task/2138 | core | degree-sequence intuition versus actual reachability — a useful reality check
:::