# 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.

## Statement

## Proofs

consider a sequence of "subrealizations", graphs whose degrees are upper bounded by the given degree sequence.

They show that, if G is a subrealization, and i is the smallest index of a vertex in G whose degree is not equal to di, then G may be modified in a way that produces another subrealization, increasing the degree of vertex i without changing the degrees of the earlier vertices in the sequence.

Repeated steps of this kind must eventually reach a realization of the given sequence, proving the theorem.

## Relation to integer partitions

## Graphic sequences for other types of graphs

Similar theorems describe the degree sequences of simple directed graphs, simple directed graphs with loops, and simple bipartite graphs ().

The first problem is characterized by the Fulkerson–Chen–Anstee theorem.

The latter two cases, which are equivalent, are characterized by the Gale–Ryser theorem.

## Stronger version

## Generalization

## See also

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Erdős–Gallai theorem.