Degree sequence of a graph

Definition

For a finite graph

Suppose $G$ is a finite undirected graph. The degree sequence of $G$ is defined as follows: for each vertex of $G$, calculate the degree of that vertex. We obtain a list (possibly with repetitions) of length equal to the size of the vertex set of $G$. The degree sequence is obtained by sorting this list in descending order (i.e., we get a non-increasing, though not necessarily a strictly decreasing, sequence).

Note that not every non-increasing sequence arises as the degree sequence of a graph.

Facts

• Handshaking lemma states that the sum of the entries of the degree sequence is twice the number of edges. In particular, it must be even.