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]