Realize or refute a degree sequence

Try

A list of proposed degrees is not automatically realizable by a simple graph. The sequence (3, 3, 1, 1) has even sum and every entry is at most three, yet two vertices adjacent to everyone force the remaining vertices to have degree at least two. A constructive reduction gives a stronger test and, when successful, builds a graph rather than merely reporting a numerical consistency check.

Predict

Predict which vertices should receive the neighbors of a vertex of largest degree d. Havel–Hakimi says that one may connect it to the d other vertices of largest remaining degrees, subtract one from those degrees, delete the chosen vertex, and repeat. A failed reduction with a negative entry or too many requested neighbors certifies impossibility. The important theorem is that this greedy neighbor choice loses no feasible realization.

Experiment

Apply the reduction to (3, 2, 2, 2, 1).

Stage	Sorted remaining degrees
Start	3, 2, 2, 2, 1
Remove degree 3 and reduce next 3	1, 1, 1, 1
Remove degree 1 and reduce next 1	1, 1, 0
Finish	0, 0

Record vertex labels during reduction so the successful steps can be reversed into actual edges. Sorting only numbers decides existence but discards the information needed to reconstruct a labeled realization.

Understand

The switching proof starts with any realization. Let v be the vertex being removed. If it misses a desired higher-degree neighbor a but meets an undesired lower-degree neighbor b, compare their neighborhoods. There is a vertex x distinct from v, a, b adjacent to a but not b: if ab is absent, b already has neighbor v while a does not; if ab is present, remove that shared adjacency from the comparison. The inequality degree (a)≥degree (b) forces an available x. Delete edges vb and ax, and add va and bx. The chosen conditions prevent loops or repeated edges, and every degree is preserved. This increases the number of desired neighbors of v. Repeat until v meets the prescribed d vertices. Deleting v then gives precisely the reduced sequence.

Apply

Conversely, any realization of the reduced sequence can be extended by a new vertex joined to the prescribed d vertices, restoring all degrees. Thus the reduction is an equivalence, not just a necessary test. The process terminates because each step removes one vertex. It is an algorithm with a proof certificate: a successful reconstruction gives an edge list whose degrees can be checked independently, while a failed step is justified by the equivalence chain. Different tie choices can produce nonisomorphic graphs with the same degree sequence; the degree sequence is not a complete graph invariant.

Continue

Use this lesson to separate three questions: whether a degree sequence is feasible, how to construct one realization, and how to enumerate or classify all realizations. Havel–Hakimi answers the first two but not the third. The proof assumes finite undirected simple graphs. Loops, parallel edges and directed in/out-degree pairs obey different constraints, so the same reduction should not be transferred without a new argument. Basic handshake reasoning remains useful as an initial check, but it cannot replace the structural theorem.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with encode a labeled tree reversibly.