Erdős–Gallai theorem

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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

Statement Erdős–Gallai theorem_section_0

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

Relation to integer partitions Erdős–Gallai theorem_section_2

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

Stronger version Erdős–Gallai theorem_section_4

Generalization Erdős–Gallai theorem_section_5

See also Erdős–Gallai theorem_section_6

Erdős–Gallai theorem_unordered_list_0


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