 Erdős–Gallai theorem

The Erdős-Gallai theorem characterizes degree sequences of finite simple graphs. A nonincreasing sequence of nonnegative integers $d_1\ge \cdots \ge d_n$ is realizable exactly when its sum is even and, for every $1\le k\le n$,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.

The Erdős–Gallai theorem is a fundamental result in graph theory that pertains to the characterization of graphs with a given number of edges. Specifically, it provides a criterion for deciding whether a graph can exist with a specified number of edges and vertices, while also satisfying certain degree conditions.