Graphic Sequence — Definition, Formula & Examples

A graphic sequence is a finite sequence of non-negative integers that can serve as the degree sequence of some simple (no loops, no multi-edges) undirected graph.

A non-increasing sequence of non-negative integers $(d_1, d_2, \ldots, d_n)$ is called graphic if there exists a simple undirected graph $G$ on $n$ vertices such that vertex $i$ has degree $d_i$ for each $i$ . Whether a sequence is graphic can be determined by the Erdős–Gallai theorem or the Hakimi algorithm (iterative application of the Erdős–Gallai conditions).

Key Formula

\sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{n} \min(d_i,\, k) \quad \text{for each } k = 1, 2, \ldots, n

Where:

$d_i$ = The $i$-th largest degree in the non-increasing sequence
$n$ = Total number of vertices (length of the sequence)
$k$ = Index from 1 to $n$ over which the inequality must hold

How It Works

To check whether a sequence is graphic, first sort it in non-increasing order. Then apply the Erdős–Gallai theorem: the sequence

(d_1, d_2, \ldots, d_n)

is graphic if and only if the sum of all degrees is even and for each

k = 1, 2, \ldots, n

the inequality

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

holds. An alternative algorithmic approach is the Erdős–Gallai/Hakimi procedure: repeatedly remove the largest degree

d_1

, subtract 1 from each of the next

d_1

entries, re-sort, and repeat until you reach all zeros (graphic) or encounter a negative entry (not graphic).

Worked Example

Problem: Determine whether the sequence (3, 3, 2, 2, 2) is graphic using the Hakimi algorithm.

Step 1: Check that the degree sum is even.

3 + 3 + 2 + 2 + 2 = 12 \quad (\text{even} \checkmark)

Step 2: Remove the first entry (3) and subtract 1 from the next 3 entries. The sequence (3, 2, 2, 2) becomes (2, 1, 1, 2). Re-sort to get (2, 2, 1, 1).

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

Step 3: Remove the first entry (2) and subtract 1 from the next 2 entries. The sequence (2, 1, 1) becomes (1, 0, 1). Re-sort to get (1, 1, 0).

(2,\, 2,\, 1,\, 1) \to (1,\, 0,\, 1) \to (1,\, 1,\, 0)

Step 4: Remove the first entry (1) and subtract 1 from the next 1 entry. The sequence (1, 0) becomes (0, 0). All entries are zero.

(1,\, 1,\, 0) \to (0,\, 0)

Answer: The sequence (3, 3, 2, 2, 2) is graphic. One realizing graph is the 5-cycle

C_5

with an added chord.

Why It Matters

Graphic sequences arise in network science when you need to determine whether a proposed degree distribution can actually be realized as a network. They also appear in combinatorics courses and are tested in graph theory qualifying exams.

Common Mistakes

Mistake: Forgetting to check that the degree sum is even before applying further tests.

Correction: An odd degree sum immediately rules out the sequence, since every edge contributes 2 to the total degree count. Always check this necessary condition first.