Graph realization problem

The graph realization problem is a decision problem in graph theory. Given a finite sequence ${\displaystyle (d_{1},\dots ,d_{n})}$ of natural numbers, the problem asks whether there is labeled simple graph such that ${\displaystyle (d_{1},\dots ,d_{n})}$ is the degree sequence of this graph.

The problem can be solved in polynomial time. One method of showing this uses the Havel–Hakimi algorithm constructing a special solution with the use of a recursive algorithm. Alternatively, following the characterization given by the Erdős–Gallai theorem, the problem can be solved by testing the validity of ${\displaystyle n}$ inequalities.

...
Wikipedia