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.
 A: 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.
