Let n be a positive integer. Let d be a list of n non-negative integers with even sum,
where the largest is less than n and differs from the smallest entry by at most 1. Prove that d is graphic.
Any THoughts?
We will call a sequence that satisfies the properties given in the problem a "good sequence". Arrange the sequence in decreasing order. What remains to show is that it satisfies the Havel-Hakimi sufficient conditions for being a graphic sequence.
Graphic Sequence -- from Wolfram MathWorld
Suppose there are p elements of value x and q elements of value x-1 initially. Remove the leftmost element from the sequence, and decrease the next x elements by 1. This is always possible since p<n. If p>x, the number of elements of value x-1 will be x+q, and the number of elements of value x will be p-x-1. If p<=x, the number of elements of value x will be 0, the number of elements with value x-1 will be p-1+n-1-x, and the number of elements of value x-2 will be x-p+1.
So in both the cases, a good sequence remains good. We again arrange it in decreasing order and repeat the whole process. In this manner, we can reduce it to a sequence of 0s and even number of 1s. Once this is done, it is easy to show that it represents a graph. So by the Havel-Hakimi conditions every good sequence is graphic.