Question on (im-)possible degree sequences of simple graphs

39 Views Asked by At

We know that I) a sequence of numbers $d_1 \geq \ldots \geq d_n$ is the degree sequence of a (not necessarily simple) graph (there exists a graph with that sequence as degree sequence) iff the sum of the elements in the sequence is even.

Furthermore II) a sequence (like above) is the sequence of a simple graph, iff $d_1 - 1, d_2 -1, \ldots, d_{d_n} - 1, d_{d_n +1}, \ldots, d_n$ is the degree sequence of a simple graph.

Now from that I would conclude that a sequence $d_1 \geq \ldots \geq d_n$ with $d_n = 1$ is never the degree sequence of a simple graph. Since either the sum of $d_1 -1 , d_2, \ldots, d_n$ or the sum of $d_1 , d_2, \ldots, d_n$ is odd and as such with II) one of them is not the degree sequence of a simple graph.

Am I missing something here?

1

There are 1 best solutions below

0
On BEST ANSWER

As suggested in the comments, the II) statement does not seem to hold.

In fact the correct formulation of the statement would be that a sequence $d_1, \ldots, d_n$ is the degree sequence of a simple graph iff, $d_2 -1, \ldots, d_{d_1} -1, \ldots, d_n$ is the degre sequence of a simple graph.

Now it is easy to see, that if $$ 2 \mid \sum_{i=1}^n d_i $$ Then also $$ 2 \mid \sum_{i=2}^{d_1} d_i -1 + \sum_{i=d_1 +1}^n d_i = \sum_{i=1} ^n d_i - 2 d_i $$ As such no such statement as I made above can be made about simple graphs.