User interface language: English | Español

Date November 2017 Marks available 2 Reference code 17N.3dm.hl.TZ0.3
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ0
Command term Use and Prove Question number 3 Adapted from N/A

Question

Consider \({\kappa _n}\), a complete graph with \(n\) vertices, \(n \geqslant 2\). Let \(T\) be a fixed spanning tree of \({\kappa _n}\).

Draw the complete bipartite graph \({\kappa _{3,3}}\).

[1]
a.i.

Prove that \({\kappa _{3,3}}\) is not planar.

[4]
a.ii.

A connected graph \(G\) has \(v\) vertices. Prove, using Euler’s relation, that a spanning tree for \(G\) has \(v - 1\) edges.

[2]
b.

If an edge \(E\) is chosen at random from the edges of \({\kappa _n}\), show that the probability that \(E\) belongs to \(T\) is equal to \(\frac{2}{n}\).

[4]
c.

Markscheme

N17/5/MATHL/HP3/ENG/TZ0/DM/M/03.a.i     A1

[1 mark]

a.i.

assume \({\kappa _{3,3}}\) is planar

\({\kappa _{3,3}}\) has no cycles of length 3     R1

use of \(e \leqslant 2v - 4\)     M1

\(e = 9\) and \(v = 6\)     A1

hence inequality not satisfied 9 \(\not  \leqslant \) 8     R1

so \({\kappa _{3,3}}\) is not planar     AG

 

Note:     use of \(e \leqslant 3v - 6\) with \(e = 9\) and \(v = 6\) and concluding that this inequality does not show whether \({\kappa _{3,3}}\) is planar or not just gains R1.

 

[4 marks]

a.ii.

a spanning tree (is planar and) has one face     A1

Euler’s relation is \(v - e + f = 2\)

\(v - e + 1 = 2\)     M1

\( \Rightarrow e = v - 1\)     AG

[2 marks]

b.

\({\kappa _n}\) has \(\left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right)\) edges \(\left( {\frac{{n(n - 1)}}{2}{\text{ edges}}} \right)\)     (A1)

\({\text{P}}(E{\text{ belongs to }}T) = \frac{{n - 1}}{{\left( {\frac{{n(n - 1)}}{2}} \right)}}\)     M1A1

clear evidence of simplification of the above expression     M1

\( = \frac{2}{n}\)     AG

[4 marks]

c.

Examiners report

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

Syllabus sections

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

View options