From a Degree Sequence to a Graph
A degree sequence records how many neighbors each vertex should have, but it does not say which vertices should be joined. The Havel-Hakimi method turns a sequence into a construction: repeatedly remove a largest degree and reduce that many other degrees, then reverse those steps to recover the edges. In this tutorial, each reduction will keep the vertex labels visible, so that the final graph is explicit rather than just a list of numbers.
When carrying out reductions, it is useful to sort the numerical degrees after every step, but sorting does not change the vertices or their labels. If several vertices have the same degree, any one of them can be chosen in that tied position. For a construction, record which labeled vertex was removed and which labeled vertices had their degrees reduced.
For the worked constructions below, we use the forward direction operationally: each recorded step is a valid Havel-Hakimi reduction. Once the reduced sequence consists only of zeros, we reconstruct the graph by adding back the removed vertices, in reverse order.
Proof. At the end of the reductions, every remaining vertex is assigned degree \(0\), so begin with those vertices and no edges. Consider a recorded reduction in reverse order. In the forward reduction, the degree of the removed vertex was deleted, and the degree of each of its recorded neighbors was decreased by \(1\). Reversing this step adds the removed vertex and one edge to each recorded neighbor. Each such neighbor therefore gains exactly the one unit removed from its degree in the forward step, and the newly added vertex has exactly the degree specified when it was removed. No other degrees change. Thus each reversed step restores the degrees from just before that reduction. Repeating through all recorded steps gives the original sequence. The construction creates no loops because each removed vertex is joined to vertices still present at that stage, and it creates no repeated edges because each removed vertex is added only once and joined once to each recorded neighbor. The graph is simple and realizes the sequence. \(\square\)
Worked Realizations
Worked Example: A Five-Vertex Sequence
Realize the sequence \((3,3,2,2,2)\). Assign the initial degrees to labeled vertices \(a,b,c,d,e\), respectively. At each reduction, the removed vertex is joined to the vertices whose degrees are decreased.
| Step | Labeled degrees before the step | Reduction | Remaining degrees, sorted |
|---|---|---|---|
| 1 | \(a3,b3,c2,d2,e2\) | Remove \(a3\); decrease \(b,c,d\) | \(b2,e2,c1,d1\): \((2,2,1,1)\) |
| 2 | \(b2,e2,c1,d1\) | Remove \(b2\); decrease \(e,c\) | \(e1,d1,c0\): \((1,1,0)\) |
| 3 | \(e1,d1,c0\) | Remove \(e1\); decrease \(d\) | \(d0,c0\): \((0,0)\) |
The final sequence is all zeros. Reverse the recorded steps. Add \(e\) joined to \(d\); then add \(b\) joined to \(e\) and \(c\); finally add \(a\) joined to \(b,c,d\). Thus the graph has vertex set \(V=\{a,b,c,d,e\}\) and edge set \(E=\{ab,ac,ad,bc,be,de\}\).
Check the degrees from this edge set: \(a\) is incident with \(ab,ac,ad\), so \(\deg(a)=3\); \(b\) with \(ab,bc,be\), so \(\deg(b)=3\); \(c\) with \(ac,bc\), so \(\deg(c)=2\); \(d\) with \(ad,de\), so \(\deg(d)=2\); and \(e\) with \(be,de\), so \(\deg(e)=2\). The degree sum is \(3+3+2+2+2=12\), and the displayed edge set has \(6\) edges, giving \(2|E|=2\cdot6=12\) as required by the handshake lemma.
Check: The computed degrees are exactly \((3,3,2,2,2)\), and the edge count agrees with half the degree sum.
Worked Example: Keeping Track of Tied Degrees
Construct a realization of \((4,3,3,2,2,2)\). Use vertices \(a,b,c,d,e,f\) with those initial degrees in that order. Several vertices tie during the reductions; record the actual choice made in each tie.
| Step | Labeled degrees before the step | Reduction | Remaining degrees, sorted |
|---|---|---|---|
| 1 | \(a4,b3,c3,d2,e2,f2\) | Remove \(a4\); decrease \(b,c,d,e\) | \(b2,c2,f2,d1,e1\): \((2,2,2,1,1)\) |
| 2 | \(b2,c2,f2,d1,e1\) | Remove \(b2\); decrease \(c,f\) | \(c1,f1,d1,e1\): \((1,1,1,1)\) |
| 3 | \(c1,f1,d1,e1\) | Remove \(c1\); decrease \(f\) | \(d1,e1,f0\): \((1,1,0)\) |
| 4 | \(d1,e1,f0\) | Remove \(d1\); decrease \(e\) | \(e0,f0\): \((0,0)\) |
Reverse the steps: add \(d\) joined to \(e\); add \(c\) joined to \(f\); add \(b\) joined to \(c,f\); and add \(a\) joined to \(b,c,d,e\). The resulting graph has \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,ad,ae,bc,bf,cf,de\}\).
Now compute each degree from the edge set. Vertex \(a\) has neighbors \(b,c,d,e\), so \(\deg(a)=4\). Vertex \(b\) has neighbors \(a,c,f\), so \(\deg(b)=3\). Vertex \(c\) has neighbors \(a,b,f\), so \(\deg(c)=3\). Vertices \(d\) and \(e\) each have the two neighbors \(a\) and the other one of \(d,e\), so each has degree \(2\). Vertex \(f\) has neighbors \(b,c\), so \(\deg(f)=2\). The degree sum is \(4+3+3+2+2+2=16\); the edge set lists \(8\) edges, and \(2\cdot8=16\).
Check: The degrees match the target sequence, including the tied degree-\(3\) vertices \(b,c\), and the independent edge count agrees with the degree sum.
Worked Example: Three Vertices of Degree One
Realize \((3,3,3,1,1,1)\), assigning the entries to \(a,b,c,d,e,f\) in that order. The example shows how vertices of degree one can remain in the reduction chain until they are joined.
| Step | Labeled degrees before the step | Reduction | Remaining degrees, sorted |
|---|---|---|---|
| 1 | \(a3,b3,c3,d1,e1,f1\) | Remove \(a3\); decrease \(b,c,d\) | \(b2,c2,e1,f1,d0\): \((2,2,1,1,0)\) |
| 2 | \(b2,c2,e1,f1,d0\) | Remove \(b2\); decrease \(c,e\) | \(c1,f1,d0,e0\): \((1,1,0,0)\) |
| 3 | \(c1,f1,d0,e0\) | Remove \(c1\); decrease \(f\) | \(d0,e0,f0\): \((0,0,0)\) |
Reversing the reductions, join \(c\) to \(f\), then \(b\) to \(c,e\), then \(a\) to \(b,c,d\). This gives \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,ad,bc,be,cf\}\).
Check the degrees explicitly: \(a\) has neighbors \(b,c,d\), so its degree is \(3\); \(b\) has neighbors \(a,c,e\), so its degree is \(3\); \(c\) has neighbors \(a,b,f\), so its degree is \(3\); and \(d,e,f\) each occur in exactly one edge, so each has degree \(1\). The degree sum is \(3+3+3+1+1+1=12\). There are \(6\) edges in the edge set, and \(2\cdot6=12\).
Check: The resulting graph has exactly the requested degrees, and the degree sum gives the same edge count as the explicit edge set.
Reading the Construction Correctly
The reduction table and the final edge set do different jobs. The table explains why the construction has the intended degrees; the edge set specifies the graph completely. Keeping both is a useful safeguard: a valid-looking chain of numbers does not by itself show which labeled vertices are adjacent, while an edge list without a degree check can conceal a missed or duplicated edge.
In a reduction, the chosen largest-degree vertex is removed, and exactly that many other entries are decreased by one. In reverse, the removed vertex is restored with edges to precisely those vertices. Do not decrease the removed vertex's neighbors in the reconstruction: their reductions have already been accounted for, and adding back the edges restores each of their lost degree units.
Common mistake: losing the labels when sorting. After the first reduction in the second example, the remaining degrees are \(b2,c2,f2,d1,e1\). Suppose one writes only \((2,2,2,1,1)\), then reduces the first \(2\) by joining it to two other entries, but forgets which labeled vertices those entries represent. The numerical sequence may still be reduced correctly, but reversing it no longer determines the edge set. The correction is to sort the labeled entries together: for example, choose \(b\), record that it is joined to \(c,f\), and then record their decreased degrees. Ties are allowed, but every choice must stay attached to its vertex label.
For these examples, a complete verification has three parts:
- Each reduction removes a largest current degree and decreases exactly the required number of other degrees.
- The reverse steps give an explicit simple graph, with its vertex and edge sets stated.
- Computing degrees from that edge set recovers the original sequence, and the edge count equals half its degree sum.
These checks reinforce one another. The reduction records the intended construction; the degree calculation tests the constructed graph vertex by vertex; and the handshake count provides an independent check on the total number of incidences. In later work, reduction chains can also be used to study sequences for which the process does not end in zeros. Here the emphasis is the constructive case: a successful chain gives a direct route from degree data to a graph.
Check Your Understanding
For each construction question, keep vertex labels attached to their degrees and verify the final edge count independently.
- For \((2,2,2,2)\), carry out a Havel-Hakimi reduction chain to zeros and give one realization by its vertex set and edge set.
- For \((3,2,2,1,1,1)\), assign the degrees to \(a,b,c,d,e,f\), record each removed vertex and its chosen neighbors, and construct the graph by reversing the steps.
- Explain why sorting the numerical degrees after a reduction must not erase the labels of the vertices.
- In a reverse construction, why does joining a restored vertex to each recorded neighbor restore the neighbors' degrees by exactly one?
- Give the degree sum and edge count for your realization of \((2,2,2,2)\), and check that they satisfy the handshake lemma.