The Erdős–Gallai theorem is a result in graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a branch of combinatorics

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

, that gives a necessary and sufficient condition for a finite sequence to be the degree sequence of a simple graph. It was obtained by Paul Erdős

Paul Erdos

Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...

 and Tibor Gallai

Tibor Gallai

Tibor Gallai was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes König and an advisor of László Lovász...

.

The statement of the theorem

A sequence of non-negative integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s can be represented as the degree sequence of a finite simple graph on n vertices if and only if is even and

holds for .

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.