△

Graph Degree Sequence Validator

Erdős–Gallai Theorem · Havel-Hakimi Algorithm · Graph Realization

Enter a sequence of integers to determine if it is a valid graphical degree sequence using the Erdős–Gallai theorem, then construct a realization via Havel-Hakimi.

Quick Examples

Degree Sequence (comma-separated, max 15 values)

Result

—

Graphical?

Sum of Degrees

—

2 × edges

Vertices

—

Edges

—

if valid

Checks & Properties

Erdős–Gallai Condition Table

For each k, the inequality ∑_i=1^k d_i ≤ k(k−1) + ∑_i=k+1ⁿ min(d_i, k) must hold.

k	Left: ∑ d_i	Right: k(k-1)+∑min	Satisfied?

Havel-Hakimi Construction Steps

Sort descending, connect the highest-degree vertex to the next d vertices, remove it, repeat.

Step	Current Sequence	Edges Added	Remaining

Graph Realization — Edge List

Graph Visualization

What Is a Degree Sequence?

In graph theory, a degree sequence is the list of degrees of all vertices in a graph, typically written in non-increasing order. The degree of a vertex is the number of edges incident to it. For example, a graph with five vertices connected as a cycle-like structure might have the degree sequence [3, 3, 2, 2, 2], indicating two vertices of degree 3 and three of degree 2.

Degree sequences serve as a compact fingerprint for graphs. They encode important structural information about connectivity, regularity, and possible topologies without specifying which vertices are connected to which.

Graphical Sequences: What Makes a Sequence Valid?

A sequence of non-negative integers is called graphical (or a graphic sequence) if it can be realized as the degree sequence of some simple graph — a graph with no self-loops and no multiple edges between the same pair of vertices. Determining graphicality is a fundamental problem in combinatorics.

Not every sequence qualifies. For instance, [3, 3, 2] is not graphical because there are only 3 vertices but the highest degree is 3, which would require connections to 3 other vertices — impossible in a 3-vertex graph. The sequence [1, 1, 1] fails because the sum (3) is odd, violating the Handshaking Lemma.

The Erdős–Gallai Theorem

The Erdős–Gallai theorem, proved by Paul Erdős and Tibor Gallai in 1960, provides a complete characterization of graphical sequences. A non-increasing sequence d₁ ≥ d₂ ≥ … ≥ dₙ of non-negative integers is graphical if and only if:

Even sum: The sum d₁ + d₂ + … + dₙ is even (Handshaking Lemma requirement).
Erdős–Gallai inequalities: For each k = 1, 2, …, n:
∑_i=1^k d_i ≤ k(k−1) + ∑_i=k+1ⁿ min(d_i, k)

The right-hand side counts the maximum possible edges: k(k-1) is the most edges within the first k vertices (a complete graph among them), and ∑ min(d_i, k) counts how many edges the remaining vertices can contribute to the first k vertices without exceeding their own degrees or k.

The Havel-Hakimi Algorithm

The Havel-Hakimi algorithm, independently proposed by Vašek Chvátal and others and formalized by Havel (1955) and Hakimi (1962), provides a constructive approach: it not only checks graphicality but also builds an actual graph realizing the sequence.

The algorithm proceeds iteratively:

Sort the degree sequence in non-increasing order.
If the first element is 0, the sequence [0, 0, …, 0] is trivially graphical (empty graph). Done.
Take the first element d₁. Connect vertex 1 to the next d₁ vertices.
Reduce the degrees of those d₁ vertices by 1. Remove vertex 1.
If any degree becomes negative, the sequence is not graphical.
Repeat with the reduced sequence.

The Havel-Hakimi theorem guarantees that a sequence is graphical if and only if the reduced sequence after each step remains graphical, providing a recursive correctness proof.

Special Graph Degree Sequences

Graph Type	Degree Sequence Pattern	Example (n=5)
Complete graph Kₙ	All n−1	[4,4,4,4,4]
Cycle Cₙ	All 2s	[2,2,2,2,2]
Path Pₙ	Two 1s, rest 2s	[2,2,2,1,1]
Star K₁,₄	One (n-1), rest 1s	[4,1,1,1,1]
Empty graph	All 0s	[0,0,0,0,0]
Regular graph	All equal k	[3,3,3,3,3,3]

Applications of Degree Sequences

Degree sequences and graphicality tests appear in many real-world contexts:

Network design: Given connectivity requirements for each node in a computer network, verify whether a valid network topology exists before hardware procurement.
Molecular chemistry: The valence sequence of atoms determines possible molecular structures. A degree sequence corresponds to a valid molecule if and only if it is graphical, with additional chemical constraints.
Social network analysis: Degree sequences model the distribution of connections in social networks. The small-world property often corresponds to specific graphical sequences with power-law characteristics.
Bioinformatics: Protein interaction networks are analyzed through their degree sequences to detect anomalies and structural motifs.
Combinatorics and extremal graph theory: Degree sequences anchor proofs of the existence of graphs with specific properties, including Ramsey theory results.

The Handshaking Lemma

The requirement that the degree sum be even is a direct consequence of the Handshaking Lemma: in any graph, the sum of all vertex degrees equals twice the number of edges (∑ deg(v) = 2|E|). This is because each edge contributes exactly 1 to the degree of each of its two endpoints. Consequently, the total degree sum must always be even, regardless of the graph's structure.

Frequently Asked Questions

What is a degree sequence?

A degree sequence is the sorted list of degrees (edge counts) of all vertices in a graph. For example, if a graph has 5 vertices and vertex degrees [3, 2, 3, 2, 2], its degree sequence written in non-increasing order is [3, 3, 2, 2, 2]. It is a compact numerical summary of the graph's connectivity structure.

What does it mean for a sequence to be "graphical"?

A sequence is graphical if there exists a simple graph (no self-loops, no multi-edges) whose vertices have exactly those degrees. Not all sequences can be realized — for example [3, 3, 2] cannot because a 3-vertex graph can have at most degree 2 per vertex in a simple graph. The Erdős-Gallai theorem provides the exact conditions to check.

How does the Erdős-Gallai theorem work?

Sort the sequence in non-increasing order. The theorem requires two conditions: (1) the sum of all degrees is even, and (2) for each k from 1 to n, the sum of the first k degrees does not exceed k(k−1) plus the sum of min(d_i, k) for the remaining vertices. The right side bounds the maximum possible edges involving those k vertices.

What is the Havel-Hakimi algorithm?

Havel-Hakimi is an iterative graph construction algorithm. At each step: sort the sequence descending, take the vertex with highest degree d, create edges from it to the next d vertices, reduce those vertices' degrees by 1, remove the processed vertex, and repeat. If any degree goes negative, the sequence is invalid. If all degrees reach zero, the edge list is a valid realization.

Why must the sum of degrees be even?

The Handshaking Lemma states that the sum of all vertex degrees equals exactly twice the number of edges: ∑ deg(v) = 2|E|. Since 2|E| is always even, any valid degree sequence must have an even sum. A sequence with an odd sum cannot correspond to any graph whatsoever.

Can two different graphs have the same degree sequence?

Yes, multiple non-isomorphic graphs can share the same degree sequence. For example, the square graph C₄ and the complete bipartite graph K₂,₂ both have degree sequence [2, 2, 2, 2], yet they are structurally different (one is a cycle, the other a bipartite graph). The Havel-Hakimi algorithm produces one valid realization; there may be many others.

What is a regular graph?

A k-regular graph is one where every vertex has exactly degree k. The degree sequence of a regular graph consists of all equal values. Examples include: the complete graph Kₙ (4-regular), the cycle Cₙ (2-regular), the Petersen graph (3-regular), and the empty graph (0-regular). Regular graphs are important in combinatorics, coding theory, and network design.