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. Paul Erdős and Tibor 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

$\sum_{i=k+1}^n \min(k,d_i)$

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 [1] 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.

[1] 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.

Would you like to stay up to date when a new post appears on the Network Pages?

Subscribe to our mailing list

Related articles

Does no small structure mean larger homogeneous ones?•••

The magic of mathematics ♠️♥️♣️♦️••

Mr Markov playing Snakes and Ladders••

How many colors do you need to color a map?••

Structure is everywhere. So is chaos.•