= Erdős-Gallai theorem
{c}
{wiki=Erdős–Gallai_theorem}
The <Erdős-Gallai theorem> characterizes <degree sequences> of finite <simple graphs>. A nonincreasing sequence of nonnegative integers $d_1\geq\cdots\geq d_n$ is realizable exactly when its sum is even and, for every $1\leq k\leq n$,
$$
\sum_{i=1}^k d_i\leq k(k-1)+\sum_{i=k+1}^n\min(k,d_i).
$$
Necessity comes from counting the edges incident with the first $k$ vertices: edges within that set contribute at most $k(k-1)$ to the degree sum, and each outside vertex can contribute at most $\min(k,d_i)$. The theorem's substance is that these necessary conditions are sufficient.
For example, $(2,2,2)$ is realized by a <triangle in a graph>. In contrast, $(3,3,1,1)$ has even sum but fails the $k=2$ inequality: $6>2+1+1$. An even sum alone therefore does not guarantee a <degree sequence>.
Back to article page
