Graph Degree Sequence Validator
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.
Your ad blocker is preventing us from showing ads
MiniWebtool is free because of ads. If this tool helped you, please support us by going Premium (ad‑free + faster tools), or allowlist MiniWebtool.com and reload.
- Allow ads for MiniWebtool.com, then reload
- Or upgrade to Premium (ad‑free)
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
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:
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:
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// from MiniWebtool, https://MiniWebtool.com/
by miniwebtool team. Updated: Feb 19, 2026
You can also try our AI Math Solver GPT to solve your math problems through natural language question and answer.