Degreesequence

Degreesequence, commonly called degree sequence, is a fundamental concept in graph theory that records how many connections each vertex has in a graph. For a simple undirected graph G with n vertices, the degree sequence is a nonincreasing sequence d1 ≥ d2 ≥ ... ≥ dn, where di is the degree of the i-th vertex. The sequence is graphical if there exists a simple graph with that degree sequence; otherwise it is non-graphical.

A basic necessary condition is the handshake lemma: the sum of the degrees equals twice the number of edges, so the sum must be even. A nonincreasing sequence with even sum may still fail to be graphical; additional conditions apply.

The Erdős–Gallai theorem provides a necessary and sufficient criterion: for every k from 1 to n, the sum of the first k degrees satisfies sum_{i=1}^k d_i ≤ k(k−1) + sum_{i=k+1}^n min(d_i, k). If these inequalities hold, the sequence is graphical. The Havel–Hakimi algorithm offers a constructive method: repeatedly remove the largest degree d1 and subtract 1 from the next d1 degrees, then resort and repeat. If this process ends with all zeros, the sequence is graphical and a corresponding graph can be realized.

A simple example is the sequence (2,2,2,2), which is graphical and realized by a 4-cycle. Degreesequences extend to multigraphs and to directed graphs (where in-degree and out-degree sequences are considered separately). They are used in studying network structure, verifying the feasibility of target degree distributions, and in random-graph models as descriptors of connectivity.