This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of
mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
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