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.
Articles by others on the same topic
The Erdős-Gallai theorem characterizes degree sequences of finite simple graphs. A nonincreasing sequence of nonnegative integers is realizable exactly when its sum is even and, for every ,Necessity comes from counting the edges incident with the first vertices: edges within that set contribute at most to the degree sum, and each outside vertex can contribute at most . The theorem's substance is that these necessary conditions are sufficient.
For example, is realized by a triangle in a graph. In contrast, has even sum but fails the inequality: . An even sum alone therefore does not guarantee a degree sequence.