# Degrees in graphs III: Which degrees sequences are possible?

In previous article, we discussed what the degree sequence of a network or graph is. Recall that a graphical sequence is a sequence of degrees that can occur in a (simple) graph. Erdős and Gallai developed a beautiful criterion to decide precisely when a degree sequence is graphical. In order to describe the Erdős-Gallai criterion, let us introduce some notation.
We denote the number of vertices in the graph by $n$, and number the degrees of the vertices by $d_1, d_2, \ldots, d_n$. This means that vertex 1 has $d_1$ neighbors, vertex 2 has $d_2$ neighbors, etc. We may assume, as in part 2, that the degrees are ordered from large to small, so that $d_1$ is the largest of the sequence $d_1, d_2, \ldots, d_n$, $d_2$ is the second largest, etc. The first requirement in the Erdős-Gallai criterion is that the sum of the degrees is even, this is the handshake lemma explained in part 1. The second requirement in the Erdős-Gallai criterion is a bit more involved. Let $k$ be an integer in between 1 and $n$. Then, the Erdős-Gallai criterion requires that, for all such $k$, the inequality
\begin{equation}
\label{Erdoes-Gallai}
\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min(k,d_i)
\end{equation}
holds. In words, if we sum the $k$ largest degrees then this cannot be more than $k(k-1)$ plus the sum of the minimum of $d_i$ and $k$, summed over the vertices that do not have the $k$ largest degrees.

Let us work this criterion out in some examples. In part 2, we showed that the sequence (3,3,1,1) is not graphical. Take $k=2$. Then, the left hand side of \eqref{Erdoes-Gallai} equals $d_1+d_2=6$. Since $k=2$, we have that $k(k-1)=2$, while $\min(k,d_i)=1$ for $i=3,4$. Thus, the inequality in \eqref{Erdoes-Gallai} does not hold for $k=2$, as it should since (3,3,1,1) is not graphical. Note that the inequality is correct though for $k=1$, as well as for $k=3$ and $k=4$, so it is necessary to check the inequality for every $k$ in between 1 and $n$. We leave it to the reader to verify that the Erdős-Gallai criterion indeed does hold in the simple graph on 7 vertices below: The Erdős-Gallai criterion looks a little mysterious. One way to see its relevance is to note that the term $\sum_{i=1}^k d_i$ on the left hand side of \eqref{Erdoes-Gallai} equals the total degree of the first $k$ vertices in the graph. This total degree consists of the edges between themselves, of which there are at most $k(k-1)$, together with the edges to the other vertices.
There can be at most $k$ edges from any vertex $i>k$ to the first $k$ vertices. Also, there cannot be more than $d_i$ edges from $i$ to the first $k$ vertices. Thus, there can be at most $\min(k,d_i)$ edges from $i$ to the first $k$ vertices, and summing this out over all vertices $i$ that are not in the first $k$ vertices gives that there are at most
\begin{equation}
\sum_{i=k+1}^n \min(k,d_i)
\end{equation}
edges between the first $k$ vertices and the other vertices. This shows that the Erdős-Gallai criterion in \eqref{Erdoes-Gallai} certainly needs to be true for any graphical sequence. However, it also sheds some light on how to produce a graph for any degree sequence that is graphical. If we can do this, then indeed the Erdős-Gallai criterion in \eqref{Erdoes-Gallai} ensures that the sequence $d_1, d_2, \ldots, d_n$ is graphical.

The proof that \eqref{Erdoes-Gallai} is really also necessary is more tricky, and will not be given here. However, we can illustrate how to construct a simple graph with the given degrees. We do this by connecting the edges one by one. Choudum  provides a proof by mathematical induction on the sum of the degrees: he lets $t$ be the first index of a number in the sequence for which $d_{t}>d_{t+1}$ (or the penultimate number if all are equal), uses a case analysis to show that the sequence formed by subtracting one from $d_t$ and from the last number in the sequence (and removing the last number if this subtraction causes it to become zero) is again graphic, and forms a graph representing the original sequence by adding an edge between the two positions from which one was subtracted.

From a practical perspective, it is also of interest how one can obtain or create a graph with the given degrees when the Erdős-Gallai criterion gives that there is one. The Havel-Hakimi algorithm is a very simple way to produce such a graph. In this algorithm, one again orders the vertices according to their degrees as $d_1\geq d_2\geq \ldots\geq d_n$. Then, we connect the $d_1$ edges of the vertex with highest degrees to the $d_1$ other vertices of maximal degree. Repeating this step (including the necessary reordering of the degrees) produces a simple graph precisely when the degree sequence is graphical. The Havel-Hakimi algorithm is thus is very simple implementation of the Erdős-Gallai criterion. You can try this out for yourself in the demo below.

DEMO: FIX n=10, PERFORM THE HAVEL-HAKIMI ALGORITHM ON degrees uniform 1-7, n=10 (add extra half-edge when sum is odd). Visually add the degrees, order them clockwise.

 Choudum, S. A. (1986), "A simple proof of the Erdős–Gallai theorem on graph sequences", Bulletin of the Australian Mathematical Society, 33 (1): 67–70, doi:10.1017/S0004972700002872, MR 823853.