Erdős–Gallai theorem

The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.

A sequence of non-negative integers ${\displaystyle d_{1}\geq \cdots \geq d_{n}}$ can be represented as the degree sequence of a finite simple graph on n vertices if and only if ${\displaystyle d_{1}+\cdots +d_{n}}$ is even and

...
Wikipedia