Exercise 33

Let $\GVE$ be a graph with $V=\{v_1,v_2,\dots,v_n\}$. Its degree sequence is the list of the degrees of its vertices, arranged in nonincreasing order. That is, the degree sequence of $\mathbf{G}$ is $(\deg_\mathbf{G}(v_1),\deg_\mathbf{G}(v_2),\dots,\deg_\mathbf{G}(v_n))$ with the vertices arranged such that $\deg_\mathbf{G}(v_1) \geq \deg_\mathbf{G}(v_2)\geq \cdots\geq \deg_\mathbf{G}(v_n)$. Below are five sequences of integers (along with $n$, the number of integers in the sequence). Identify

• the one sequence that cannot be the degree sequence of any graph;
• the two sequences that could be the degree sequence of a planar graph;
• the one sequence that could be the degree sequence of a tree;
• the one sequence that is the degree sequence of an eulerian graph; and
• the one sequence that is the degree sequence of a graph that must be hamiltonian.

Explain your answers. (Note that one sequence will get two labels from above.)

1. $n=10$: $(4,4,2,2,1,1,1,1,1,1)$

2. $n=9$: $(8,8,8,6,4,4,4,4,4)$

3. $n=7$: $(5,4,4,3,2,1,0)$

4. $n=10$: $(7,7,6,6,6,6,5,5,5,5)$

5. $n=6$: $(5,4,3,2,2,2)$