Degree bounds
0 ≤ dᵢ ≤ n − 1
A vertex can connect to at most every other vertex once.
Degree Sequence Graphicality Checker — Havel–Hakimi Algorithm
Enter a degree sequence
Keyboard shortcut: Ctrl+Enter or ⌘+Enter checks the sequence.
Private by design: degree data is processed on this device. It is not uploaded, saved, or added to the page URL.
Advertisement
What is a graphical degree sequence?
A finite sequence d₁, d₂, …, dₙ is graphical if some finite simple undirected graph has exactly those vertex degrees. “Simple” means there are no self-loops or repeated edges. The order of the input values does not matter, so the algorithm first sorts them from largest to smallest.
Handshaking lemma
Σdᵢ = 2|E|
The degree sum must be even, and half of it is the required edge count.
Havel–Hakimi reduction
(d₁,…,dₙ) → (d₂−1,…,d₍d₁₊₁₎−1,…,dₙ)
After sorting, remove d₁ and reduce the next d₁ entries.
How the Havel–Hakimi algorithm works
1. Sort
Arrange the current degrees in nonincreasing order while retaining a vertex label for graph construction.
2. Remove the maximum
Take the first value d. The corresponding vertex must be adjacent to d other vertices.
3. Reduce the next d values
Connect that vertex to the next d highest-degree vertices and subtract one from each of their remaining degrees.
4. Repeat or stop
All zeros prove graphicality. Needing more remaining vertices than exist, or forcing a negative degree, proves the sequence is not graphical.
The theorem says the original sorted sequence is graphical if and only if its reduced sequence is graphical. Repeating that equivalence makes the test conclusive, not merely a heuristic.
Havel–Hakimi example
For (3, 3, 2, 2, 2), repeatedly sort and reduce:
- Remove 3 and subtract one from the next three values: (3,2,2,2) → (2,1,1,2), then sort to (2,2,1,1).
- Remove 2 and reduce the next two: (2,1,1) → (1,0,1), then sort to (1,1,0).
- Remove 1 and reduce the next one: (1,0) → (0,0).
The process ends in zeros, so the sequence is graphical. Its degree sum is 12, meaning every realization has 12 ÷ 2 = 6 edges. The checker labels vertices by input position and displays one realization.
By contrast, (3,3,3,1) eventually forces a remaining zero below zero. An even degree sum alone therefore does not guarantee graphicality.
Input rules, assumptions, and limits
Enter between 1 and 500 base-10 nonnegative integers. Commas, semicolons, spaces, tabs, and line breaks are accepted as separators. Decimal values, signs, scientific notation, words, and empty input are rejected. Leading zeros are accepted and normalized.
The result concerns finite simple undirected graphs only. A zero represents an isolated vertex. Input position supplies deterministic labels v1, v2, …; equal degrees are resolved by those labels, so repeated checks construct the same witness. A different graph may realize the same sequence.
The complete edge list is constructed for every supported graphical sequence. To avoid a crowded or slow diagram, the SVG preview is shown only for at most 24 vertices and 80 edges. The step table and CSV remain available for larger cases.
The reduction theorem and constructive interpretation follow S. L. Hakimi’s original paper, On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I, published in 1962 by the Society for Industrial and Applied Mathematics.
Calculation note: graphical and nongraphical sequences, isolated vertices, complete graphs, odd sums, impossible maximum degrees, reduction failures, witness degrees, separators, and input limits checked by the Starlight Tools editorial team. Last reviewed: .
Degree sequence checker FAQ
What is a graphical degree sequence?
It is a finite list of nonnegative integers that occurs as the vertex-degree list of at least one finite simple undirected graph.
How does the Havel–Hakimi algorithm work?
Sort the values, remove the largest value d, subtract one from the next d values, and sort again. Reaching all zeros means graphical. An impossible reduction means nongraphical.
Does an even degree sum prove the sequence is graphical?
No. Every graphical sequence has an even sum, but some even-sum sequences still fail Havel–Hakimi. For example, (3,3,3,1) has sum 10 but is not graphical.
What type of graph does this checker use?
A finite simple undirected graph. Each edge joins two different vertices, there is at most one edge per vertex pair, and edge direction is not used.
Can multiple graphs have the same degree sequence?
Yes. The degree sequence records only how many neighbors each vertex has, not which vertices are adjacent. The displayed witness is one deterministic realization.
Are zeros allowed?
Yes. Each zero represents an isolated vertex. For example, (0,0,0) is graphical as three vertices with no edges.
Why is a degree greater than n − 1 impossible?
In a simple graph with n vertices, one vertex has only n − 1 other vertices available as distinct neighbors. A larger degree would require a self-loop or a repeated edge.
Does this calculator upload my degree sequence?
No. The test, witness construction, copy action, and CSV generation run in your browser. This tool does not store or transmit the entered sequence.