Calculator Inputs
Example Data Table
| Example Sequence | Sorted Form | Graphical? | Edges | Comment |
|---|---|---|---|---|
| 3, 3, 2, 2, 2 | 3, 3, 2, 2, 2 | Yes | 6 | This sequence passes both main tests and has a valid realization. |
| 4, 4, 1, 1, 1, 1 | 4, 4, 1, 1, 1, 1 | No | 6 | The reduction or inequality check fails before a simple graph can exist. |
| 2, 2, 2, 2 | 2, 2, 2, 2 | Yes | 4 | This is the degree pattern of a simple cycle on four vertices. |
| 0, 0, 0, 0 | 0, 0, 0, 0 | Yes | 0 | This corresponds to an empty graph with four isolated vertices. |
Formula Used
1. Handshaking Lemma
For any simple undirected graph, the sum of all vertex degrees equals twice the number of edges.
sum(degrees) = 2 × edges
2. Basic Feasibility Rules
Every degree must be non-negative, and no degree may exceed n − 1, where n is the number of vertices.
3. Havel-Hakimi Reduction
Sort the degrees from largest to smallest. Remove the first value d. Subtract 1 from the next d values. Repeat until all values become zero or a contradiction appears.
4. Erdos-Gallai Inequality
For a non-increasing sequence d1 ≥ d2 ≥ ... ≥ dn, the sequence is graphical only if the degree sum is even and, for each k from 1 to n:
sum(i=1 to k) di ≤ k(k − 1) + sum(i=k+1 to n) min(di, k)
How to Use This Calculator
Step 1
Enter the degree sequence as integers. You may separate values with commas, spaces, semicolons, or new lines.
Step 2
Choose how you want the sequence displayed. Descending order is often easiest for graph theory checks.
Step 3
Set a vertex label prefix if you want the realization table to use custom labels like n1, n2, n3, or a1, a2, a3.
Step 4
Press the analyze button. The result appears above the form and below the header, as requested.
Step 5
Review the pass or fail checks, the Havel-Hakimi steps, the Erdos-Gallai table, and the plotted degree values.
Step 6
Use the CSV or PDF buttons to export the analysis for class notes, assignments, or record keeping.
Frequently Asked Questions
1. What is a degree sequence?
A degree sequence is a list of vertex degrees from a graph. Each number tells how many edges touch that vertex in an undirected network.
2. What does graphical mean?
Graphical means there exists at least one simple undirected graph whose vertex degrees match the sequence exactly.
3. Why must the degree sum be even?
Every edge contributes 2 to the total degree count, one for each endpoint. That makes the sum of degrees always even.
4. What is the Havel-Hakimi method?
It is a reduction process that repeatedly removes the largest degree and subtracts 1 from the next several terms. Failure proves the sequence is not graphical.
5. What is the Erdos-Gallai test used for?
It checks a family of inequalities that must hold for every valid degree sequence. It provides a second rigorous confirmation beside Havel-Hakimi.
6. Can zero values appear in the sequence?
Yes. A zero means that vertex is isolated and has no incident edges. Zero values are valid in simple graph degree sequences.
7. Does one graphical sequence give only one graph?
No. Many different simple graphs can share the same degree sequence. The calculator shows one possible realization, not every realization.
8. Why can a sequence fail even when all values look small?
Small values alone are not enough. The parity rule, upper bounds, and structural inequalities must all agree before a valid simple graph exists.