Erdos-Gallai Theorem

For discussing Olympiad Level Combinatorics problems
User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh
Erdos-Gallai Theorem

Unread post by Masum » Tue Jun 05, 2012 4:26 pm

Definition: Let's call sequence $\{d_i\}_{i=1}^n$ graphic if $d_1,d_2...,d_n$ can be used as a degree of the vertex of a graph.
Now, prove that $d_i$ is graphic iff for every $1\le k\le n$ \[\sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}min(d_i,n)\] and $\sum\limits_{i=1}^nd_i$ is even.
One one thing is neutral in the universe, that is $0$.

Post Reply