Graphic Sequences (Erdős–Gallai)

Decide if a degree sequence is realizable via Havel–Hakimi and Erdős–Gallai.

The idea

The degree sequence of a graph is the list of its vertex degrees, written in decreasing order. A list $d_{1} \ge d_{2} \ge \cdots \ge d_{n}$ of nonnegative integers is graphic if it is the degree sequence of some simple graph — no loops, no repeated edges — and such a graph is said to realize the list. This topic decides, from the list alone, whether a realizing graph exists.

A list can fail to be graphic in two ways. It can fail on arithmetic: every edge adds $1$ to the degree of each of its two endpoints, so the degrees of any graph sum to an even number, and a list with an odd sum is not graphic. It can also pass the parity check and fail on structure: $(3, 3, 3, 1)$ has even sum $10$, but in a simple graph on four vertices a vertex of degree $3$ must neighbor all three others, so three such vertices would force the fourth to have degree $3$ rather than $1$.

Two criteria settle the question completely: the Havel–Hakimi reduction, which wires the top-degree vertex to the $d_{1}$ next-highest-degree vertices and then deletes it, one vertex at a time, and the Erdős–Gallai inequalities, which test the list directly.

Ways to work on it

• Walkthrough. Parity, the Havel–Hakimi reduction, and what realizability means.
• Practice. Run Havel–Hakimi to decide whether a sequence is graphic.
• Hardest. Decide whether an even-sum sequence is graphic via the Erdős–Gallai inequality.

Not sure where to start? Take the ten-question placement test.