Chapter 14 · Special Topics
Degree Sequences and Graphical Sequences
The handshaking lemma's consequences, Erdős–Gallai and Havel–Hakimi — which one to use when you must build the graph.
#Realisability
A sequence d1 ≥ d2 ≥ … ≥ dn ≥ 0 is graphical if some simple graph has exactly these degrees. deg(v) = degree; ∑v deg(v) = 2m (handshaking).
Immediate necessary conditions (all of them cheap to check)
- ∑ di is even (handshaking);
- d1 ≤ n - 1, and more: ∑i=1k di ≤ k(k-1) + ∑i>k min(di, 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 d1 = 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 ∑ di = 2n - 2 (construct with Prüfer codes, Counting Trees: Cayley and Prüfer).
#Erdős–Gallai
∑ di is even and for every 1 ≤ k ≤ n,
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(di, 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
d is graphical iff d1 = 0 (all zero) or, with d1 = k > 0, the sequence obtained by deleting d1 and subtracting 1 from the next k entries (then re-sorting) is graphical.
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) ≥ deg(w) with v adjacent to some neighbour x of... concretely, if uw ∈ E, uv ∉ E and there is x with xv ∈ E, xu ∉ 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
// 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
- only need yes/no, n ≤ 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(n2), which is 2.5×107 and fine,
- need the graph: Havel–Hakimi with a heap/insertion into a sorted array, O(n2) or O(nm), and it produces the edges,
- need it to be connected: the clean sufficient condition is 2 ≤ dn ≤ d1 ≤ n-1 and ∑ di even — then Erdős–Gallai applied to the shifted sequence yields a connected realisation (Anstee's characterisation adds the prefix inequalities ∑i=1k di ≥ 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 di ≥ 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, Max Flow: Ford–Fulkerson, Dinic, Push–Relabel).
#Regularity and the two classic traps
A k-regular graph on n vertices exists iff 0 ≤ k < n and nk is even. Trap 1: people add "n ≥ 3" or "simple" conditions that are unnecessary (the cycle gives 2-regular for all n ≥ 3; two vertices give 1-regular; k = n-1 is Kn). 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 ≡ 0,1 ±od 4 since C(n, 2) must be even).
#Realisation in a contest statement
"Given n and the multiset of degrees, count the graphs" — hard (no known closed form; only n ≤ 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: ∑ a = ∑ b and ∑i=1k ai ≤ ∑j min(bj, k) for all k, with the same greedy proof. Know the three variants so a statement never surprises you.