Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Shouldn't that $d_k$ on the left side of the display be $d_i$? –  Gerry Myerson Apr 20 '11 at 13:05
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks for the resources. –  Hobbie Apr 22 '11 at 3:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.