Graph Degree Sequence Calculator
Test a degree sequence with Havel–Hakimi and print a realisation, or the exact reason none exists.
Graph Degree Sequence Calculator
Test a degree sequence with Havel–Hakimi and print a realisation, or the exact reason none exists.
What the page prints, and what it refuses
Every figure is printed with the rule or formula that produced it, and any numerical tolerance is stated on the result rather than implied. The page refuses an input the formula does not define and names the value it read; it prints no answer it cannot support.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page answers whether a list of degrees belongs to a simple graph, and if it does, it prints one graph with those degrees. The sequence 3, 3, 2, 2, 2 is graphical; the realisation it prints has six edges over five vertices.
Two necessary conditions are checked first and named when they fail: the degrees must sum to an even number, and no degree may reach the number of vertices. Then Havel–Hakimi either builds the graph or proves that none exists.
How Havel–Hakimi decides
Sort the residual degrees. Take the largest, connect it to that many of the next largest, reduce those degrees, and repeat. If at any step there are too few positive vertices left, no simple graph exists.
The process is exact and finite: each step removes one vertex. The printed realisation is one witness, not the only graph with that sequence, and the page says so.
How to use Graph Degree Sequence Calculator
Enter the degrees separated by spaces, commas or new lines, then press Run.
The result prints the verdict, the degree sum, the edge count and one realisation as a list of vertex pairs.
What to Expect
Best for
- Testing a degree sequence before drawing it
- Getting one graph with given degrees
- Seeing why an odd degree sum is impossible
Not ideal for
- Enumerating every graph with a sequence
- Multi-edges or self-loops, which are not simple graphs
- More than 200 vertices
What this tool keeps
- Every degree in the order typed
What may need cleanup
- Nothing: the verdict and realisation are exact
Common errors
- An odd sum is refused with the reason
- A degree at or above n is refused with the reason
Example use cases
- Test 3, 3, 2, 2, 2
- See 1, 1, 1 fail on an odd sum
- Build a graph for a tournament schedule
Sample input
3, 3, 2, 2, 2
Sample output
graphical: yes, with 6 edges and the realisation (0, 1) (0, 2) (0, 3) (1, 2) (1, 4) (3, 4)
Who this is for
- Graph theory students
- Readers checking a degree sequence
Frequently asked questions
Why must the degree sum be even?
Every edge adds one to the degree of each of its two ends, so the sum counts each edge twice. An odd sum therefore cannot come from any graph.
Is the printed graph the only one?
No. Many graphs can share a degree sequence, and the page prints one witness. The verdict is about existence, not uniqueness.
What about self-loops?
This page models simple graphs, so a loop that adds 2 to one degree is outside the model. The realisation uses distinct vertex pairs only.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.