Degree (graph Theory) - Degree Sequence

The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a graph invariant so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence.

The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops. The question of whether a given degree sequence can be realized by a simple graphs is more challenging. The Erdős–Gallai theorem states that a non-increasing sequence of n numbers d_i (for i = 1,...,n) is the degree sequence of a simple graph if and only if the sum of the sequence is even and

For instance, the sequence (3, 3, 3, 1) is not the degree sequence of a simple graph; it satisfies the Erdős–Gallai inequality when k is 1, 2, or 4 but not when k = 3.

Havel (1955), and later, Hakimi (1962) proved that (d₁, d₂, ..., d_n) is a degree sequence of a simple graph if and only if (d₂ − 1, d₃ − 1, ..., d_d1+1 − 1, d_d1+2, d_d1+3, ..., d_n) is. This fact leads to a simple algorithm for finding a simple graph that has a given realizable degree sequence:

1. Begin with a graph with no edges.
2. Maintain a list of vertices whose degree requirement has not yet been met in non-increasing order of residual degree requirement.
3. Connect the first vertex to the next d₁ vertices in this list, and then remove it from the list. Re-sort the list and repeat until all degree requirements are met.

The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of graph enumeration.