Talk:Erdős–Gallai theorem
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
I am afraid the proof of Erdos-Gallai outlined in the description is not correct (the sufficiency part).
The sequence 6, 6, 6, 6, 5, 5, 2, 2 is graphic, that is there is a simple graph with these degrees. On the other hand if we revise the sequence as suggested in the proof, we obtain 6, 6, 6, 6, 5, 4, 2, 1 and this is not graphic since the first k=4 numbers do violate the inequality of Erdos and Gallai:
6 + 6 + 6 + 6 is strictly larger than 4(4-1) + (4+4) + (2+1)
Andras Frank
frank@cs.elte.hu
- It looks like Choudom's proof was inaccurately described: t should be the first index for which d_t < d_{t+1}, not the last. So that would take the sequence 6,6,6,6,5,5,2,2 to 6,6,6,5,5,5,2,1. Thanks for finding this mistake. —David Eppstein (talk) 16:26, 28 March 2013 (UTC)