Press "Enter" to skip to content

The Erdős-Gallai theorem on the degree sequence of finite graphs

Cubic graph
Cubic graph (source: Wikipedia)

In a finite graph \( {G=(V,E)} \), the degree of a vertex \( {i\in V} \) is the number \( {d(i)} \) of vertices connected directly to \( {i} \) by an edge:

\[ d(i)=\mathrm{card}\{j\in V:\{i,j\}\in E\}. \]

We say that the graph \( {G} \) is \( {d} \)-regular where \( {d\geq0} \) is a fixed integer when \( {d(i)=d} \) for all \( {i\in V} \). The \( {0} \)-regular graphs are formed by isolated vertices and do not have any edge. The \( {1} \)-regular graphs are formed by disconnected edges. The \( {2} \)-regular graphs are formed by disconnected cycles and infinite chains.

The Erdős-Gallai theorem states that for any integers \( {n\geq1} \) and \( {d_1\geq\cdots\geq d_n\geq0} \), there exists a graph with \( {n\geq1} \) vertices with respective degrees \( {d_1,\ldots,d_n} \) if and only if the following two conditions hold true:

  1. the integer \( {d_1+\cdots+d_n} \) is even;
  2. for any \( {1\leq k\leq n} \), \( {d_{1}+\cdots+d_{k}\leq k(k-1)+ \min(k,d_{k+1})+\cdots+\min(k,d_{n})} \).

In this case we say that \( {d_1,\ldots,d_n} \) is graphic. The fact that the sum \( {d_1+\cdots+d_n} \) is even comes from the fact that each edge counts twice. The quantity \( {k(k-1)+\min(d_{k+1},k)+\cdots+\min(d_{n},k)} \) is the maximum contribution to \( {d_1+\cdots+d_k} \) of the edges connected to the vertices \( {1} \) to \( {k} \): at most \( {\binom{k}{2}=k(k-1)/2} \) edges (count twice) between the vertices \( {1} \) to \( {k} \), and at most \( {\min(k,d_{k+i})} \) edges between the vertex \( {i>k} \) and the vertices \( {1} \) to \( {k} \). We say that \( {d_1,\ldots,d_n} \) is the degree sequence of the graph.

In particular, for a \( {d} \)-regular graph with \( {n} \) vertices, we have \( {d_1=\cdots=d_n=d} \) and the Erdős-Gallai theorem states that \( {d} \) is even and \( {kd\leq k(k-1)+(n-k)\min(k,d)} \) for every \( {1\leq k\leq n} \), which gives in particular \( {d\leq n-1} \) and equality is achieved for the complete graph.

The Erdős-Gallai theorem was proved by Paul Erdős and Tibor Gallai in a paper published in 1960 in hungarian. Nowadays, many proofs are available, including one by Claude Berge. A short and constructive proof can be found in a paper by Amitabha Tripathi, Sushmita Venugopalan, and Douglas West.

Further reading. Lecture notes on random graphs by Remco van der Hofstad, and by Charles Bordenave, none of which contains a proof of the Erdős-Gallai theorem.

3 Comments

  1. Djalil Chafaï 2015-10-24

    A colleague of mine asked if for any integers n>d>1 there exists an oriented d regular graph (we say ofter a digraph) with n vertices, in the sense that each of the n vertices has exactly d in-coming edges and d out-coming edges. The answer is positive, as one can check with the n by n circulant matrix with exactly d consecutive 1 on each row (it is the adjacency matrix of such a graph). This corresponds to put the n vertices on a circle (Z/nZ if one prefers) and to connect each vertex with the d vertices above it, modulo n.

  2. Gerard Letac 2015-12-31

    Comment decrire la condition d’Erdos Gallai en termes de diagramme de Young?

Leave a Reply

Your email address will not be published. Required fields are marked *