# Proving a degree sequence is graphical

I've been given the following assignment question:

Let $n\ge1$ and let $S = d_1, d_2, ..., d_n$ be a list of $n$ non-negative integers where:

1. $d_1\ge d_2\ge...\ge d_n$

2. $\sum^n_{i=1} d_i$ is even

3. $d_1<n$

4. $1 \ge d_1 - d_n \ge 0$

Prove that S is graphical.

I've gotten so far as mentioning that because of (1) and (4), there are two cases: $d_1 = d_n$ and $d_1 = d_n + 1$ since the difference is either 0 or 1 because they're both integers. I've then stated that in the first case, if all the degrees are the same, then the graph is a complete graph and $d_i = n - 1$ for all values of i, so it's graphical.

What I'm having trouble with is showing the second case is graphical. Originally I split it up into $n$ being odd and $n$ being even as different versions of the second case, but I'm not sure if that's the right path to follow. I was thinking about trying the Erdos-Gallai theorem, but the fact that there aren't any values given is throwing me off, and the Havel-Hakami theorem also only seems useful to me if there are values, but I'm sure I'm missing something.

Any help would be greatly appreciated.

If $d_1 = d_n$, that does not necessarily tell you that the graph is a complete graph. For example, you might have $d_1 = d_2 = \dots = d_{100} = 3$, which is a $3$-regular graph on $100$ vertices. In general, conditions (1) and (4) together tell us that the vertex degrees are all either $k$ or $k-1$ for some value $k$ with $1 \le k < n$. So having $d_1 = d_2 = \dots = d_{20}=4$ and $d_{21} = d_{22} = \dots = d_{100}=3$ is also possible.
The Havel–Hakimi theorem is in fact very useful here. When you apply it to a degree sequence like $(4, 4, 4, 3, 3, 3, 3, 3, 3)$, you get $(3, 3, 2, 2, 3, 3, 3, 3)$: after we sort it, $(3, 3, 3, 3, 3, 3, 2, 2)$. This also satisfies the conditions in your problem.
So what you can try to prove is that this happens in general: whenever you have a degree sequence that starts at $k$ and ends at either $k$ or $k-1$, this is also true of the degree sequence you get after applying Havel–Hakimi. Then turn this into a proof by induction (on $n$, the number of vertices).