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.