Simplification of the Erdos-Gallai Theorem

Question

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.

Answer 1

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.