# Simplification of the Erdos-Gallai Theorem

A week or two ago back I was pointed to the Erdos-Gallai Theorem in this question.

I've been unable to locate a satisfactory proof of this theorem, since the reference on wikipedia is in Hungarian. I'm particularly curious to see the proof of just one direction.

Suppose you are already given that a degree sequence $(d_1,\ldots,d_n)$ is graphic. How could you then show $$\sum_{i=1}^k d_i\leq k(k-1)+\sum_{i=k+1}^n\min(k,d_i)?$$ A suggestion I read said to think about any set $U$ of $k$ vertices, and then consider how many edges have at least one end vertex in that set $U$. My guess is $k$, one connected to each vertex in $U$, but I don't see how that is very insightful. Is there a nice way of showing the above implication.

-

1
Shouldn't that $d_k$ on the left side of the display be $d_i$? – Gerry Myerson Apr 20 '11 at 13:05

## 1 Answer

Page 3-4 of Blitzstein and Diaconis's paper "A Sequential Importance Sampling Algorithm For Generating Random Graphs With Prescribed Degrees" has a brief discussion.

Quoting from the paper:

The necessity of these conditions is not hard to see: for any set $S$ of $k$ vertices in a realization of $d$, there are at most $\binom{k}{2}$ "internal" edges within $S$, and for each vertex $v \notin S$, there are at most $\min(k, \deg(v))$ edges from $v$ into $S$. The sufficiency of the Erdos-Gallai conditions is more difficult to show....

From their paper, they give a reference to:

• Berge, C. (1976). Graphs and Hypergraphs, Elsevier, New York.
• Choudum, S. A. (1986). A simple proof of the Erdos-Gallai theorem on graph sequences. Bulll. Austral. Math. Soc. 33, 1, 67-70 (pdf)
• Tripathi, A. and Vijay, S. (2003). A note on a theorem of Erdos & Gallai. Discrete Math. 265, 1-3, 417-420

and of course the original paper that you found in hungarian:

• Erdos, P. and Gallai, T. (1960). Graphen mit punkten vorgeshriebenen grades. Math. Lapok 11, 264-274.

Searching around I also found a short paper by Tripathi, Venugopalan and West here.

Hope that helps.

-

Thanks for the resources. – Hobbie Apr 22 '11 at 3:19
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9218740463256836, "perplexity_flag": "middle"}