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:
- the integer \( {d_1+\cdots+d_n} \) is even;
- 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