Degree Sequence — Definition, Formula & Examples

A degree sequence is the list of vertex degrees of a graph, arranged in non-increasing order. It summarizes how connected each vertex is without specifying the exact edges.

Given a graph $G = (V, E)$ with $n$ vertices, the degree sequence is the sequence $(d_1, d_2, \ldots, d_n)$ where $d_i = \deg(v_i)$ for each vertex $v_i \in V$ , ordered so that $d_1 \geq d_2 \geq \cdots \geq d_n$ .

How It Works

To find the degree sequence, count the number of edges incident to each vertex. Then sort those counts from largest to smallest. Two graphs with different degree sequences cannot be isomorphic, so the degree sequence serves as a quick first test when comparing graphs. However, two non-isomorphic graphs can share the same degree sequence, so it is a necessary but not sufficient condition for isomorphism.

Worked Example

Problem: Find the degree sequence of a graph with vertices

\{A, B, C, D, E\}

and edges

\{AB, AC, AD, BC, DE\}

Count degrees: Count the edges touching each vertex:

\deg(A) = 3,\; \deg(B) = 2,\; \deg(C) = 2,\; \deg(D) = 2,\; \deg(E) = 1

Sort in non-increasing order: Arrange the degrees from largest to smallest.

(3,\, 2,\, 2,\, 2,\, 1)

Verify with the Handshaking Lemma: The sum of degrees should equal twice the number of edges. There are 5 edges, so the sum should be 10.

3 + 2 + 2 + 2 + 1 = 10 = 2 \times 5 \;\checkmark

Answer: The degree sequence is

(3, 2, 2, 2, 1)

Visualization

Why It Matters

Degree sequences appear in network analysis, where they characterize the connectivity pattern of social networks, biological networks, and communication systems. The Erdős–Gallai theorem uses degree sequences to determine whether a given sequence of integers can actually be realized as a simple graph, a foundational question in combinatorics and algorithm design.

Common Mistakes

Mistake: Forgetting to sort the sequence in non-increasing order.

Correction: An unsorted list of degrees is just a degree list, not a degree sequence. Always arrange values from largest to smallest so the sequence is canonical and comparable across graphs.