User interface language: English | Español

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\);

[2]
a.

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

[3]
b.

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

[3]
c.

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]

a.

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]

b.

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]

c.

Examiners report

[N/A]
a.
[N/A]
b.
[N/A]
c.

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.7 » Graphs, vertices, edges, faces. Adjacent vertices, adjacent edges.
Show 29 related questions

View options