Determine if a graph exists knowing the degree of its vertices

Question

Problem: There is a graph on ten vertices whose degrees are $9,8,8,8,6,5,4,4,2,2$

Answer: False.

My attempt: Since we know that $2 | E | = \sum _ { v \in V } d ( v )$, $$2\cdot 28 = 9+8\cdot3+6+5+4\cdot2+2\cdot2$$ Hence $| E | = 28$. Since we don't now more about the graph (it may not be a tree), how can I determine that such graph does not exist?

Answer 1

Suppose it is simple and without loops.

If that one exist then if we delete node with degree $9$ and it edges, we would get a graph:

$$7,7,7,5,4,3,3,1,1$$

now if we delete node of degree $7$ and it edges we get

$$6,6,4,3,2,2,1,0\;\;\;\;{\rm or} \;\;\;\;\geq 6,?,?,?,?,?,0,0$$

Second situation is impossible since at least one node of degree $0$ must be connected with first one with degree at least 6.

So suppose 1. situation is possible, then it is also: $$5,3,2,1,1,0$$

but this is actualy impossible (since at least one node of degree $0$ must be connected with first one with degree at least 5).

So such a graph does not exist.

Answer 2

The answer is FALSE.

We proceed with the Havel–Hakimi Theorem, which determines whether a degree sequence can represent a simple graph.

Applying this theorem, we note that the original degree sequence is graphical if and only if the degree sequence given by $\{7, 7, 7, 5, 4, 3, 3, 2, 1\}$ is graphical. We can keep on reiterating to get the following degree lists:

$$\{6, 6, 4, 3, 2, 2, 1, 0\} \rightarrow \{5, 3, 2, 1, 1, 0, 0\} \rightarrow \{2, 1, 0, 0, 0, -1\}$$

But, the last degree list is clearly not graphical: it has an edge with a negative degree! So, the answer is false.