Bezoek de website voor leraren en scholieren →

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
\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min(k,d_i)
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.