What does 'graphical' mean for a degree sequence?

A degree sequence is graphical if there exists at least one simple graph (no loops or multiple edges) whose vertices have exactly those degrees.

What is the Handshake Lemma?

It states that the sum of all vertex degrees in any graph is always even, since every edge contributes exactly 2 to the total (one for each endpoint) — so an odd sum immediately rules out a sequence as graphical.

What is the Erdős–Gallai theorem?

It's a necessary and sufficient condition for a sequence to be graphical: sorted in descending order, the sum of the first k terms must be at most k(k−1) plus the sum of min(dᵢ, k) for the remaining terms, for every k from 1 to n.

Why check every value of k?

Each k represents a potential 'overcrowding' scenario — checking whether the k highest-degree vertices could possibly have enough edges available (to each other and to the rest) without exceeding what the remaining vertices can supply.

What happens if the largest degree exceeds n − 1?

In a simple graph with n vertices, no vertex can have more than n − 1 neighbors (it can't connect to itself or duplicate an edge), so any degree exceeding n − 1 makes the sequence automatically non-graphical.

Is a graphical sequence's graph unique?

No — multiple different graphs can share the same degree sequence. The Erdős–Gallai theorem only confirms that at least one such graph exists, not which one.

How large a sequence can this calculator handle?

This calculator supports sequences up to 100 values long, checking all Erdős–Gallai conditions instantly even at that size.

Where is this used in real life?

It's used in network design and social network analysis to check whether a proposed set of connection counts is even physically realizable before trying to construct the actual network.

Graph Degree Sequence Validator — Check If a Degree Sequence Is Graphical

Our Graph Degree Sequence Validator checks whether a given sequence of non-negative integers can actually be the degree sequence of some simple graph, applying the Erdős–Gallai theorem's prefix-sum conditions directly and reporting exactly which condition fails if the sequence isn't graphical.

Quick Answer

Enter a degree sequence below to instantly check whether it's graphical (realizable as an actual graph) via the Erdős–Gallai theorem.

Degree sequence

Enter whole numbers separated by commas or spaces, e.g. 3,3,2,2,1,1.

How to Use the Graph Degree Sequence Validator — Erdős–Gallai Theorem Online

1
Enter a degree sequence as comma- or space-separated whole numbers, e.g. 3,3,2,2,1,1.
2
Click 'Calculate' to check whether the sequence is graphical.
3
Review the step-by-step verification of the Erdős–Gallai conditions.

Why Use Graph Degree Sequence Validator — Erdős–Gallai Theorem Online?

Not every list of numbers can be the degree sequence of an actual graph — the Erdős–Gallai theorem gives an exact test: sort the sequence in descending order, and for every prefix length k, the sum of the first k degrees must not exceed k(k−1) plus the sum of min(degree, k) over the remaining vertices. A sequence passing every one of these prefix conditions (and having an even total, by the Handshake Lemma) is guaranteed to be realizable as a simple graph. This calculator runs that exact check and reports precisely where it fails, if it does.

Frequently Asked Questions

Related Tools

Adjacency Matrix Calculator — Build a Graph Matrix Online

Build and display the adjacency matrix of a graph from a simple edge-list input, along with its degree sequence. Free calculator, weighted or unweighted.

Graph Coloring Calculator — Welsh-Powell Algorithm Online

Color a graph's vertices so no two connected nodes share a color, using the greedy Welsh-Powell algorithm. Free calculator with a simple edge-list input.

Planar Graph Checker — Kuratowski-Style Test Online

Check whether a graph is planar using the E ≤ 3V−6 necessary condition plus an explicit K₅/K₃,₃ subgraph search for small graphs. Free calculator, not a full planarity test.