a graph cannot exist with a degree sequence of $1,{\text{ }}2,{\text{ }}3,{\text{ }}4,{\text{ }}5,{\text{ }}6,{\text{ }}7,{\text{ }}8,{\text{ }}9$;

a simple, connected, planar graph cannot exist with a degree sequence of $4,{\text{ }}4,{\text{ }}4,{\text{ }}4,{\text{ }}5,{\text{ }}5$;

a tree cannot exist with a degree sequence of $1,{\text{ }}1,{\text{ }}2,{\text{ }}2,{\text{ }}3,{\text{ }}3$.

assume such a graph exists

by the handshaking lemma the sum of the degrees equals twice the number of edges     R1

but $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45$ which is odd     R1

this is a contradiction so graph does not exist     AG

[2 marks]

assume such a graph exists

since the graph is simple and connected (and $v = 6 > 2$) then $e \leqslant 3v - 6$     R1

by the handshaking lemma $4 + 4 + 4 + 4 + 5 + 5 = 2e$ so $e = 13$     A1

hence $13 \leqslant 3 \times 6 - 6 = 12$     A1

this is a contradiction so graph does not exist     AG

[3 marks]

assume such a graph exists

a tree with 6 vertices must have 5 edges (since ${\text{V}} - {\text{E}} + 1 = 2$ for a tree)     R1

using the Handshaking Lemma $1 + 1 + 2 + 2 + 3 + 3 = 2 \times 5$ implies $12 = 10$     M1A1

this is a contradiction so graph does not exist     AG

[3 marks]