Erdős-Gallai Theorem

The Erdős-Gallai theorem gives a necessary and sufficient criterion for a finite sequence of nonnegative integers to be a graphic sequence. In one form, a nonincreasing degree sequence ${d_1,...,d_n}$ is graphic iff is even and

for each integer .

Explore with Wolfram|Alpha

More things to try:

Ai(3) to 100 places
complete the square x^2+10x+28
mean {21.3, 38.4, 12.7, 41.6}

References

Erdős, P. and Gallai, T. "Graphs with Prescribed Degrees of Vertices." Mat. Lapok. 11, 264-274, 1960.Tripathi, A. and Vijay, S. "A Note on a Theorem of Erdős & Gallai." Discr. Math. 265, 417-420, 2003.

Cite this as:

Weisstein, Eric W. "Erdős-Gallai Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Erdos-GallaiTheorem.html

Erdős-Gallai Theorem

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications