Graph Degree Sequence Validator

Q: What is the Erdos-Gallai theorem?

The Erdos-Gallai theorem provides a set of inequalities that a non-increasing sequence of non-negative integers must satisfy to be graphical. A sequence d1 >= d2 >= ... >= dn is graphical if and only if the sum is even and for each k from 1 to n, the sum of the first k terms is at most k(k-1) plus the sum of min(dk, k) over the remaining terms. The Havel-Hakimi algorithm is often preferred in practice because it is simpler to implement.

Use the Havel-Hakimi algorithm to determine if a given sequence of numbers can form a simple, undirected graph. Features animated step-by-step visualization, adjacency matrix, and a sample graph rendering.

Free to useNo sign-up requiredUpdated Feb 2026

Graph Degree Sequence ValidatorTry it now — free ▼

Embed Graph Degree Sequence Validator Widget

About Graph Degree Sequence Validator

Welcome to the Graph Degree Sequence Validator, a powerful tool that uses the Havel-Hakimi algorithm to determine whether a given sequence of non-negative integers can form a simple, undirected graph. This tool provides animated step-by-step visualization of the algorithm, an interactive graph rendering for valid sequences, and a full adjacency matrix — making it ideal for students, educators, and researchers in graph theory and discrete mathematics.

What is a Degree Sequence?

In graph theory, a degree sequence is a monotonic non-increasing sequence of the vertex degrees of a graph. The degree of a vertex is the number of edges incident to it. For example, in a triangle (3 vertices, 3 edges), every vertex has degree 2, so the degree sequence is (2, 2, 2).

A degree sequence is called graphical if there exists at least one simple graph (no self-loops, no multi-edges) whose vertex degrees match that sequence. Not every sequence of non-negative integers is graphical — for example, (3, 1, 1) is not graphical because one vertex would need 3 connections but only 2 other vertices exist.

The Havel-Hakimi Algorithm

The Havel-Hakimi algorithm (named after Václav Havel and Samuel Louis Hakimi) is a recursive algorithm that determines whether a given finite sequence of non-negative integers is graphical. It is one of the most elegant algorithms in discrete mathematics.

Algorithm Steps

function HavelHakimi(sequence):
  while sequence is not empty:
    Sort sequence in non-increasing order
    Remove leading zeros
    if sequence is empty: return GRAPHICAL
    d ← first element // largest degree
    Remove first element
    if d > remaining count: return NOT GRAPHICAL
    Subtract 1 from each of the next d elements
    if any element becomes negative: return NOT GRAPHICAL
  return GRAPHICAL

Havel-Hakimi Theorem

For $ n \geq 1 $, the non-increasing sequence $ d_1 \geq d_2 \geq \cdots \geq d_n $ of non-negative integers is graphical if and only if the sequence

$$d_2 - 1,\; d_3 - 1,\; \ldots,\; d_{d_1+1} - 1,\; d_{d_1+2},\; \ldots,\; d_n$$

is graphical.

The Handshaking Lemma

A fundamental prerequisite for any degree sequence is the Handshaking Lemma:

Handshaking Lemma

$$\sum_{i=1}^{n} d_i = 2|E|$$

The sum of all vertex degrees equals twice the number of edges.

This immediately implies that the sum of a degree sequence must be even. If the sum is odd, the sequence cannot possibly be graphical — no graph realization exists.

Erdos-Gallai Theorem

An alternative characterization of graphical sequences is given by the Erdős–Gallai theorem:

Erdős–Gallai Theorem

A non-increasing sequence $ d_1 \geq d_2 \geq \cdots \geq d_n $ is graphical if and only if the sum is even and for each $ k = 1, 2, \ldots, n $:

$$\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k)$$

While the Erdős–Gallai theorem gives a closed-form characterization, the Havel-Hakimi algorithm is often preferred in practice for its simplicity and the fact that it constructively builds the graph.

How to Use This Tool

Enter a degree sequence: Type a list of non-negative integers separated by commas or spaces. Use the quick examples to get started.
Click Validate: The tool checks the parity condition and runs the Havel-Hakimi algorithm.
Watch the animation: Use the step controls (Play, Next, Show All, Reset) to visualize each iteration of the algorithm.
Explore the result: For graphical sequences, view a sample graph rendering and adjacency matrix.

Understanding the Results

Verdict: Whether the sequence is graphical (can form a simple graph) or not.
Parity Check: Whether the sum of degrees is even (a necessary condition).
Algorithm Steps: Each iteration of Havel-Hakimi with color-coded element tracking.
Graph Visualization: A sample simple graph that realizes the degree sequence (if graphical).
Adjacency Matrix: The 0/1 matrix representation of the sample graph.

Applications of Degree Sequences

Network Design

When designing communication or transportation networks, engineers need to know if a desired connectivity pattern is achievable. Degree sequence validation ensures that the planned network topology is realizable before committing resources.

Social Network Analysis

In social science, researchers model social networks as graphs. The degree sequence describes the distribution of connections. Validating whether an observed degree distribution can form a simple network helps in modeling and simulation studies.

Bioinformatics

Protein interaction networks and gene regulatory networks are modeled as graphs. Degree sequence analysis helps researchers understand network properties and generate random graphs with the same degree distribution for null model testing.

Algorithm Design Education

The Havel-Hakimi algorithm is a cornerstone of discrete mathematics courses. It demonstrates key concepts: greedy algorithms, induction, and graph realization. This tool helps students visualize and understand each step of the algorithm.

Frequently Asked Questions

What is a degree sequence in graph theory?

A degree sequence is a list of non-negative integers that represents the number of edges connected to each vertex in a graph. For example, the sequence (3, 2, 2, 1) means one vertex has 3 edges, two vertices have 2 edges each, and one vertex has 1 edge. A valid (graphical) degree sequence must have an even sum, since each edge contributes 2 to the total degree.

What is the Havel-Hakimi algorithm?

The Havel-Hakimi algorithm is a recursive method to determine if a finite sequence of non-negative integers can be the degree sequence of a simple graph. It works by repeatedly sorting the sequence in descending order, removing the largest element d, and subtracting 1 from the next d elements. If the process reduces to all zeros, the sequence is graphical; if a negative number appears or d exceeds the remaining count, it is not.

What does it mean for a sequence to be graphical?

A sequence of non-negative integers is called graphical if there exists a simple, undirected graph (no self-loops, no multiple edges) whose vertices have exactly those degrees. For example, (2, 2, 2) is graphical because it can form a triangle (3 vertices each connected to the other 2), while (3, 1, 1) is not graphical because a single vertex cannot connect to 3 others when only 2 other vertices exist.

Why must the sum of a degree sequence be even?

This is a consequence of the Handshaking Lemma, which states that the sum of all vertex degrees in any graph equals twice the number of edges. Since twice any integer is even, the sum of the degree sequence must be even. This is a necessary (but not sufficient) condition for a sequence to be graphical.

What is the Erdos-Gallai theorem?

The Erdős-Gallai theorem provides a set of inequalities that a non-increasing sequence of non-negative integers must satisfy to be graphical. A sequence d1 >= d2 >= ... >= dn is graphical if and only if the sum is even and for each k from 1 to n, the sum of the first k terms is at most k(k-1) plus the sum of min(dk, k) over the remaining terms. The Havel-Hakimi algorithm is often preferred in practice because it is simpler to implement.

Additional Resources

Reference this content, page, or tool as:

"Graph Degree Sequence Validator" at https://MiniWebtool.com/graph-degree-sequence-validator/ from MiniWebtool, https://MiniWebtool.com/

by miniwebtool team. Updated: Feb 19, 2026

Developer API available: Run this tool from your app, automation, or agent with one JSON HTTP request. View API docs