Graphs · step 7 of 14

Degree sequences & graphic sequences

A sequence is graphic if some simple graph has exactly those degrees. Three checks in order settle nearly every case: the sum must be even (handshake), no term may exceed n − 1, and then the Havel–Hakimi reduction either terminates in all zeros or produces a negative entry. Havel–Hakimi is both a test and a construction.

Practise degree sequences & graphic sequences free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Check the parityAn odd degree sum is immediately non-graphic.
Check the rangeEvery degree must lie between 0 and n − 1 for a simple graph.
Run Havel–HakimiSort descending, remove the largest degree d, subtract 1 from the next d entries, re-sort, repeat.
Read the verdictAll zeros means graphic (and the steps reconstruct a graph). A negative entry means not graphic.

Worked example

Is (4, 3, 3, 2, 2) graphic?

Sum = 14, even ✓. Max degree 4 ≤ 5 − 1 = 4 ✓.
Remove 4, subtract 1 from the next four: (3,3,2,2) → (2,2,1,1).
Remove 2, subtract 1 from the next two: (2,1,1) → (1,0,1); re-sort to (1,1,0).
Remove 1, subtract 1 from the next one: (1,0) → (0,0). All zeros.

Answer. Graphic — Havel–Hakimi terminates in all zeros, and reversing the steps builds a realising graph.

Where marks get dropped

These are the specific errors that cost credit on degree sequences & graphic sequences questions — QED's rubric penalises each of them separately.

Forgetting to re-sort after each reduction. Havel–Hakimi requires descending order at every step.
Subtracting from the wrong entries. You reduce the d LARGEST remaining degrees, not arbitrary ones.
Concluding "graphic" from the parity check alone. (4,4,1,1) has an even sum but is not graphic on 4 vertices.

Practise this until it is automatic

Unlimited fresh questions

QED generates new degree sequences & graphic sequences problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Degree sequences & graphic sequences — frequently asked questions

Why does Havel–Hakimi work?

Because if any realisation exists, one exists where the highest-degree vertex is joined to the next highest degrees — a standard edge-swapping argument. Removing that vertex reduces the problem.

What is the Erdős–Gallai condition?

An inequality characterising graphic sequences directly, checking partial sums against a bound for each k. It gives the same answer without iteration.

Does graphic mean the graph is unique?

No. Many non-isomorphic graphs can share a degree sequence, which is why degree sequences are a weak isomorphism invariant.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make degree sequences & graphic sequences exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →