Introduction
We assume familiarity with finite simple undirected graphs, vertex degrees, paths and the idea of replacing some edges of a graph by others.
The question is simple to state. Someone hands us a finite list of integers, such as . Is there a simple graph whose vertices have exactly these degrees? If so, how do we build one?
Some lists fail for obvious reasons, and some fail for subtler ones. The Havel–Hakimi theorem settles every case. It reduces the question for a list of length to the same question for a list of length . The reduction is constructive, so it also produces a graph whenever one exists.
Graphical lists
Throughout, a graph is a finite simple undirected graph. It has no loops and no multiple edges. We write for a set of labeled vertices.
Definition 8.2.1
(Graphical list and realization)
Let and let be a list of integers. We say is graphical if there is a simple graph on the vertex set with
Such a is called a realization of .
Three points about this definition deserve attention.
- The empty list is graphical. When , the empty graph has no vertices, and every condition on its vertices holds vacuously.
- Every all-zero list is graphical. For of length , the edgeless graph on vertices is a realization.
- Labels matter, but only up to relabeling. Entry is attached to vertex . If is a permutation of , then is graphical if and only if is graphical. To see this, rename the vertices of a realization. So we may sort a list without changing whether it is graphical. We must, however, record which vertex each entry belongs to if we want a realization on the original labels.
A list with a negative entry is never graphical, because a degree counts edges and is at least .
Two necessary conditions
Suppose is graphical with realization , and let be the number of edges of .
Proposition 8.2.2
(Necessary degree conditions)
If is graphical and its realization has edges, then
so the sum of the entries is even, and
Proof
(Counting edge ends and possible neighbors)
Handshake parity. Each edge contributes exactly to the degree of each of its two distinct endpoints, so the degrees add up to twice the number of edges.
Degree bound. In a simple graph, vertex can be adjacent only to the other vertices, each at most once.
Both conditions are necessary. Neither, nor even the two together, is sufficient.
Counterexample mode
Even sum and bounded entries, yet not graphical
Take and . The sum is , which is even. Every entry lies between and . Both necessary conditions hold.
Suppose were a realization. Vertex has degree , so it is adjacent to all of . The same is true of , so it is adjacent to all of . Then is adjacent to both and , so . This contradicts . Hence is not graphical.
The lesson is that parity and the degree bound are local, counting-level constraints. Graphicality also depends on how the large degrees interact. Two vertices of large degree force edges onto everyone else.
The Havel–Hakimi theorem
The intuition is greedy. The vertex with the largest demand should be satisfied first. It should be joined to the vertices that have the most remaining demand, since those are hardest to satisfy later. After those edges are fixed, the vertex is finished and can be deleted. What remains is a shorter list of leftover demands.
Theorem 8.2.3
(Havel–Hakimi theorem)
Let and let be integers with
Define the residual list of length , indexed by , by
In words, delete and subtract from each of the next entries. Then is graphical if and only if is graphical. In particular, if has a negative entry, then is not graphical.
The hypothesis guarantees , so the entries exist. The residual need not be sorted. Because sorting does not affect graphicality, we sort before applying the theorem again.
Proof
Write and , so that . The only property of the proof uses is this: every vertex in has degree at least as large as every vertex outside .
Proof
(Add a vertex; switch edges, then delete it)
Reverse direction ( graphical graphical). Let be a realization of on , so . Since is graphical, its entries are nonnegative. Form by adding a new vertex and the edges for .
These new edges are distinct, because their other endpoints are distinct. None of them is a loop, because . None of them was already present, because is new. So is simple. In , vertex has degree . Each has degree . Each other vertex keeps degree . Hence realizes .
Forward direction ( graphical graphical). We first show that some realization of has , where is the set of neighbors of .
Key step: one edge switch. Let be any realization of with . Since , there is a vertex . There is also a vertex . Then , , and , since and .
Let and . Whether or not is an edge, the same correction is subtracted from both degrees, so
Now contains none of (there are no loops), (by definition) or (since ). So . On the other hand, because . So the neighbors of inside form the set , which has size .
Therefore . There exists a vertex with:
- adjacent to ;
- not adjacent to ;
- .
The four vertices are pairwise distinct. In :
- and are edges;
- and are non-edges.
Define by removing the edges and and adding the edges and .
The graph is simple. Neither added edge is a loop, since and . Neither was present before. The two added edges are different from each other.
Degrees are unchanged:
- loses and gains ;
- loses and gains ;
- loses and gains ;
- loses and gains .
So is again a realization of .
Progress. The neighborhood of changed only by removing and adding . Every neighbor of already in is kept, and
The quantity is at most . Repeating the switch therefore reaches, after at most switches, a realization of with .
Deletion. Delete from . Each loses exactly one neighbor. Every other vertex loses none. The result is a simple graph on with degrees . So is graphical. In particular, if is graphical, then has no negative entry.
Proof X-ray
Where the largest-degree choice is used
The reverse direction is bookkeeping: a new vertex joined to raises exactly the degrees that were lowered. All the content is in the forward direction, and in one move, the degree-preserving switch that trades the edges for .
The hypothesis that consists of vertices of largest remaining degree is used exactly once, in . Its job is to produce the fourth vertex : since , some neighbor of outside is not a neighbor of . Without the inequality need not exist. In the exercise on decrementing smaller entries, with and the path , the choice , gives , and no switch is possible.
The four distinct vertices and the pattern of two edges and two non-edges are what keep simple with unchanged degrees. The process terminates because rises by one per switch and is at most . The argument shows that the greedy neighborhood can always be made part of some realization, not that every realization contains it.
Ties, termination and the realization algorithm
Ties. If several entries equal , any one of them may play the role of . If and entries tie across the boundary, that is, , any vertices of largest remaining degree may receive the decrement. The proof used only that each vertex in has degree at least that of each vertex outside . The verdict "graphical or not" is therefore independent of how ties are broken. The graph produced may depend on the choice.
Labeled realization algorithm. Maintain a list of pairs (residual degree, vertex label) and an initially empty edge set .
- Input check. If some entry is negative, or some entry exceeds , reject. If , accept with .
- If all residual degrees are , accept and output . This includes the case where the list has become empty.
- Sort the pairs by residual degree, largest first. Let be the first pair, and let be the current number of pairs. If , reject.
- Remove . For each of the next pairs , replace by and add the edge to .
- If any residual degree is now negative, reject. Otherwise return to step 2.
Termination. Each pass through step 4 shortens the list by one, so there are at most passes.
Correctness. We argue by induction on the length, applying the theorem at each step. Two further facts complete the argument.
- is simple. Once is removed it never reappears, so every edge recorded at its step joins to a distinct vertex that is still present. No edge is recorded twice.
- has the right degrees. Fix a vertex , and suppose it has residual when it is removed. Then has received edges earlier and receives edges at its own step, for a total of . If is never removed, its residual at acceptance is , and it has received all edges.
After the input check, step 3 cannot actually trigger: the invariant is that every residual entry is at most when the current length is . Initially this is exactly the input bound. If the largest entry is less than , every remaining entry is at most , hence at most . If , every remaining entry is decremented and again becomes at most . Thus the bound holds at the next length ; step 5 separately rejects negative values. Keeping the test in step 3 is harmless.
Running time. Count comparisons and arithmetic on degrees of size at most as unit-cost operations, and append each edge in amortized constant time. Use any comparison sort costing per pass. Each pass also does decrements and edge insertions, and there are at most passes. The total cost is
The output has at most edges, which fits within this bound. This is a simple polynomial upper bound. We make no claim that it is optimal.
Concept lensCombinatorial
An inequality certificate instead of a reduction
For a nonincreasing list with even sum, graphicality is also equivalent to a system of inequalities, the Erdős–Gallai conditions:
Necessity is a count of edge ends at : edges inside this set contribute at most , and each outside vertex contributes at most . For and the inequality reads , which fails. The algorithm builds a realization; a failed inequality certifies that none exists.
Worked examples
Worked example 8.2.4
(A graphical list with an explicit edge set)
Let on . The sum is , so a realization, if one exists, has edges.
- Pass 1. Remove (degree ). Decrement . Record edges . Residual: .
- Pass 2. Sorted order is . Remove . Decrement . Record . Residual: .
- Pass 3. Sorted order is . Remove . Decrement . Record . Residual: . All zero, so accept.
The edge set is
Check the degrees:
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
There are edges, as predicted.
The explorer below replays the labeled Havel–Hakimi passes on a degree list, ending either with a verified edge set or with a negative residual that proves the list is not graphical.
Worked example 8.2.5
(An even-sum list rejected at a negative entry)
Return to .
- Pass 1. Remove (degree ). Decrement , giving .
- Pass 2. Sorted order is . Since , the bound test passes. Remove and decrement , giving .
A negative entry appears, so is not graphical. By the theorem, neither is . This agrees with the direct argument above.
The negative entry has a concrete meaning. After and are satisfied, vertices and would have to accept more edges than they demand.
Worked example 8.2.6
(One list, non-isomorphic realizations)
Let .
- Pass 1. Remove and decrement . Record .
- Pass 2. Sorted order is (each ), then (each ). Remove and decrement . Record .
- Pass 3. Now each have residual . Remove and decrement . Record .
- Pass 4. Now . Remove and decrement . Record . All residuals are now zero, so accept.
The output consists of two disjoint triangles, on and on .
The -cycle also realizes . The cycle is connected and the two triangles are not, so the two graphs are not isomorphic.
What a graphical sequence does not determine
Three notions must be kept apart.
- Graphicality. This is a yes/no property of a list. The theorem decides it.
- Labeled realizations. Even when the labeled degrees are fixed, there may be several realizations. For there are exactly three labeled realizations, one for each perfect matching of . Those three graphs are distinct as labeled graphs but isomorphic.
- Isomorphism type. A degree multiset does not determine a graph up to isomorphism, as the worked example on non-isomorphic realizations shows. Conversely, the lists and have the same multiset but different labels. They are realized by the paths and , which are different labeled graphs and isomorphic graphs.
Yes: any two realizations of the same labeled list are joined by a finite sequence of degree-preserving switches.
A natural next question
Are any two realizations linked by edge switches?
Yes: any two realizations of the same labeled list are joined by a finite sequence of degree-preserving switches.
The forward proof already does most of the work. Given realizations and of , switches turn each into a realization in which has neighborhood . Deleting leaves two realizations of , and induction on connects them by switches that never touch . Reversing the switches applied to completes a chain from to . In particular, the two disjoint triangles and the 6-cycle above are linked in this way.
Common mistakes
Two errors have already been met: treating parity and the bound as sufficient, which refutes, and allowing loops or repeated edges, which every graph here excludes.
Common mistake
(Subtracting from the wrong entries)
The theorem decrements the next largest entries. The exercise on decrementing smaller entries shows that doing so can wrongly reject a graphical list.
Common mistake
(Forgetting to re-sort)
The residual may be out of order, and the next pass must start from its largest entry. In the first worked example the residual must be reordered so that is decremented in the second pass.
Common mistake
(Switching the wrong pair of edges)
The switch removes the edges and and inserts the non-edges and . Removing makes no sense, because is not an edge.
Exercises
Quick check
(Decide whether is graphical.)
Solution
The sum is , which is even, and every entry is at most .
- Pass 1. Remove and decrement the next four entries. This gives , which is already sorted.
- Pass 2. Remove and decrement the next three entries. This gives .
A negative entry appears, so the list is not graphical.
Directly: two vertices of degree among five vertices are adjacent to every other vertex. Then each remaining vertex has degree at least , but .
Quick check
(Show that is graphical. Use the algorithm to construct a labeled realization, and verify every degree.)
Solution
- Pass 1. Remove (degree ). Decrement . Record . Residual: each have .
- Pass 2. Remove and decrement . Record . Residual: .
- Pass 3. Sorted order is . Remove and decrement . Record . All residuals are zero, so accept.
The edge set is
Check the degrees:
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
- is adjacent to , so its degree is .
There are edges, matching the sum .
Quick check
(Let . Prove that no list of pairwise distinct integers is graphical.)
Solution
Suppose is graphical with pairwise distinct entries. Every entry lies in , which has exactly elements. Since the entries are distinct, every value in this set occurs. In particular, some vertex has degree and some vertex has degree . Since , these are different vertices.
Vertex is adjacent to all other vertices, including . So , which is a contradiction.
Quick check
(The list is graphical. Show this. Then join to and instead of to the largest remaining entries, and show that the resulting residual is not graphical. Explain why this does not contradict the theorem.)
Solution
The path has degrees at . So is graphical.
Now join to and . The residual is , that is, . Applying the theorem to it gives , so is not graphical.
There is no contradiction. The theorem guarantees success only when is joined to vertices of largest degree, here and one of . Doing that gives the residual or , and both are graphical. The forward proof needed for and . With , the vertex outside has strictly larger degree, so the switching argument does not apply.