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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.