# 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.

 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.