Date | November 2016 | Marks available | 2 | Reference code | 16N.3dm.hl.TZ0.2 |
Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
Command term | Explain | Question number | 2 | Adapted from | N/A |
Question
In this question no graphs are required to be drawn. Use the handshaking lemma and other results about graphs to explain why,
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\).
Markscheme
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]