Talk:Erdős–Gallai theorem

Latest comment: 11 years ago by David Eppstein

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)Reply