Mathematics.

fundamentals

Degree Sequences

Graph Theory25 minDifficulty4 out of 10

You should know: graph basics

Overview

The degree sequence of a graph is the list of all vertex degrees, usually sorted in non-increasing order. It's a simple invariant — just count edges at each vertex — but it packs a surprising amount of structural information: it instantly tells you the number of edges (via the handshaking lemma), and a purely arithmetic test (the Erdős–Gallai theorem) tells you whether ANY simple graph could ever produce a given sequence, without having to construct one. Not every list of non-negative integers is a valid degree sequence — a sequence that passes the test is called 'graphical'. Degree sequences show up whenever a network's connectivity pattern matters more than its exact wiring: internet router degree distributions, social network 'friend counts', and chemistry (atom valences in molecular graphs) are all degree-sequence questions in disguise.

Intuition

Think of the degree sequence as a shopping list of 'how many connections does each person need' at a party. The handshaking lemma is just double counting: every handshake (edge) gives exactly 2 people a tally mark, so the total tally is always even — an odd degree sum is an instant red flag that no graph can match it. The Erdős–Gallai condition is a sharper version of the same idea: it checks that the k neediest people don't demand more handshakes than the room can physically supply, once you account for how many handshakes the remaining guests can each contribute.

Formal Definition

Definition

For a graph G = (V, E) with vertices v₁, …, vₙ, the degree sequence is (deg(v₁), …, deg(vₙ)) sorted so that d₁ ≥ d₂ ≥ … ≥ dₙ. The Erdős–Gallai theorem characterizes exactly which sequences are graphical:

∑i=1ndi=2∣E∣\sum_{i=1}^{n} d_i = 2|E|
Handshaking lemma: degree sum is always even
∑i=1kdi  ≤  k(k−1)+∑i=k+1nmin⁡(di,k)for each 1≤k≤n\sum_{i=1}^{k} d_i \;\le\; k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k) \quad \text{for each } 1 \le k \le n
Erdős–Gallai condition (must hold for every k)

Worked Examples

  1. Sum the degrees.

    3+3+2+2+1+1=123+3+2+2+1+1 = 12

  2. By the handshaking lemma, the sum of degrees is twice the number of edges.

    ∣E∣=12/2=6|E| = 12 / 2 = 6

Answer: 6 edges.

Practice Problems

Difficulty 3/10

A graph has degree sequence (5, 4, 3, 2, 2). How many edges does it have?

Difficulty 4/10

Explain why (3, 3, 3, 1, 1) cannot be the degree sequence of any simple graph.

Difficulty 6/10

A network engineer proposes connecting 5 routers so their connection counts (degrees) are (4, 4, 4, 4, 4). Verify this is achievable and identify what topology it forces.

Quiz

The handshaking lemma says the sum of all vertex degrees in a graph equals:
A proposed degree sequence has an odd sum. What can you immediately conclude?
The Erdős–Gallai theorem is used to determine:

Summary

  • The degree sequence lists each vertex's degree, usually sorted in non-increasing order.
  • Handshaking lemma: Σdeg(v) = 2|E| — the degree sum is always even and equals twice the edge count.
  • An odd degree sum instantly rules out a sequence; the Erdős–Gallai theorem gives the full test for whether a sequence is 'graphical'.
  • The Havel–Hakimi algorithm constructively realizes a graphical sequence as an actual graph.

References

  1. WebsiteWikipedia — Degree (graph theory)
  2. WebsiteWikipedia — Erdős–Gallai theorem