# Erdős–Gallai theorem

The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. Erdős–Gallai theorem_sentence_0

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. Erdős–Gallai theorem_sentence_1

A sequence obeying these conditions is called "graphic". Erdős–Gallai theorem_sentence_2

The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named. Erdős–Gallai theorem_sentence_3

## Proofs Erdős–Gallai theorem_section_1

consider a sequence of "subrealizations", graphs whose degrees are upper bounded by the given degree sequence. Erdős–Gallai theorem_sentence_4

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. Erdős–Gallai theorem_sentence_5

Repeated steps of this kind must eventually reach a realization of the given sequence, proving the theorem. Erdős–Gallai theorem_sentence_6

## Graphic sequences for other types of graphs Erdős–Gallai theorem_section_3

Similar theorems describe the degree sequences of simple directed graphs, simple directed graphs with loops, and simple bipartite graphs (). Erdős–Gallai theorem_sentence_7

The first problem is characterized by the Fulkerson–Chen–Anstee theorem. Erdős–Gallai theorem_sentence_8

The latter two cases, which are equivalent, are characterized by the Gale–Ryser theorem. Erdős–Gallai theorem_sentence_9