Graph Degree Sequence Validator

What is a Graphic Degree Sequence?

A degree sequence is a list of non-negative integers representing the degrees of the vertices in a graph. A degree sequence is called graphic if there exists a simple, undirected graph (no loops or multiple edges) that realizes it. The Havel-Hakimi algorithm provides an efficient method to determine whether a given sequence is graphic.

The Havel-Hakimi Algorithm

Given a degree sequence $d_1, d_2, \dots, d_n$ sorted in non-increasing order, the algorithm works as follows:

If all degrees are zero, the sequence is graphic (empty graph).
If the first degree $d_1$ is negative or greater than the number of remaining vertices, the sequence is not graphic.
Remove $d_1$ and subtract 1 from the next $d_1$ degrees.
Sort the new sequence in non-increasing order and repeat from step 1.

Explore related mathematical tools like the Matrix Determinant Calculator and Column Space Calculator.

Key Theorems

Handshaking Lemma: In any graph, the sum of all vertex degrees is even (every edge contributes 2 to the sum). A necessary condition for a sequence to be graphic is that its sum is even.

Erdős–Gallai Theorem: A non-increasing sequence $d_1 \geq d_2 \geq \dots \geq d_n$ is graphic if and only if $\sum_{i=1}^n d_i$ is even and for all $1 \leq k \leq n$:

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

How to Use This Validator

Enter a degree sequence — Type non-negative integers separated by commas (e.g., "3,3,3,3,2").
Watch the algorithm — The Havel-Hakimi algorithm steps are shown in detail with each iteration.
Check the verdict — The validator tells you whether the sequence is graphic or not.
Try examples — Use the preset examples to explore different types of degree sequences.

Applications

Degree sequence validation is fundamental in graph theory and network analysis. It is used in random graph generation (e.g., the configuration model for generating random graphs with a given degree distribution), network design and verification, social network analysis to determine if a connection pattern is realizable, and computational chemistry for molecular structure validation. For more graph and matrix tools, check the Eigenvalue Eigenvector Calculator or Combinations Permutations Calculator.

Frequently Asked Questions

What is a degree sequence?

A degree sequence is a list of the degrees of each vertex in a graph. For a graph with $n$ vertices, the degree sequence is a list of $n$ non-negative integers, where each integer represents how many edges are incident to that vertex. For simple graphs (no loops or multiple edges), each degree is at most $n - 1$.

What does "graphic" mean in this context?

A degree sequence is called "graphic" if there exists at least one simple, undirected graph that has exactly that degree sequence. If such a graph exists, we say the sequence is realizable or graphic. The Havel-Hakimi algorithm provides both a necessary and sufficient condition for a sequence to be graphic.

What is the Handshaking Lemma?

The Handshaking Lemma states that in any graph, the sum of all vertex degrees equals twice the number of edges: $\sum \deg(v) = 2|E|$. This means the sum of degrees must always be even. If a degree sequence has an odd sum, it cannot be graphic — this is the first check that the Havel-Hakimi algorithm performs.

Can a sequence with odd sum be graphic?

No. The Handshaking Lemma proves that the sum of degrees in any graph must be even. If your sequence has an odd sum, it is automatically not graphic, and the Havel-Hakimi algorithm will terminate immediately with this result.

What is the configuration model?

The configuration model is a method for generating random graphs with a given degree sequence. It works by assigning each vertex a number of "half-edges" or "stubs" equal to its target degree, then randomly pairing stubs to form edges. If the degree sequence is graphic, the configuration model can produce a simple graph (after resolving possible multi-edges and loops).

How does the Erdős–Gallai theorem differ from Havel-Hakimi?

Both provide conditions for a degree sequence to be graphic, but they work differently. The Havel-Hakimi algorithm is constructive and iterative, actually building the sequence step by step. The Erdős–Gallai theorem provides a set of inequalities that must hold for all $k$, which is more useful for theoretical analysis. In practice, the Havel-Hakimi algorithm is simpler to implement and understand.

Report