Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/fontdata.js

User interface language: English | Español

Date May 2008 Marks available 12 Reference code 08M.3dm.hl.TZ2.5
Level HL only Paper Paper 3 Discrete mathematics Time zone TZ2
Command term Show that Question number 5 Adapted from N/A

Question

Let G be a simple, connected, planar graph. 

(a)     (i)     Show that Euler’s relation fe+v=2 is valid for a spanning tree of G.

  (ii)     By considering the effect of adding an edge on the values of  fe and v show that Euler’s relation remains true.

(b)     Show that K5 is not planar.

Markscheme

(a)     (i)     A spanning tree with v vertices and (v −1) edges where = 1     A1A1

f e + v =1 − (v − 1) + v = 2     M1

So the formula is true for the tree     AG

 

(ii)     Adding one edge connects two different vertices, and hence an extra face is created     M1R1

This leaves v unchanged but increases both e and f by 1 leaving f e + v unchanged. Hence f e + v = 2 .     R1R1

[7 marks]

 

(b)     Using e ,     M1

for {K_5},{\text{ }}v = 5 and e = \left( {\begin{array}{*{20}{c}}   5 \\   2 \end{array}} \right) = 10     A1A1

but 3v − 6 = 3(5) − 6 = 9     A1

9 is not greater or equal to 10 so {K_5} is not planar     R1

[5 marks]

Total [12 marks]

Examiners report

Part (a)(i) was done successfully but many students did not read part(ii) carefully. It said ‘adding an edge’ nothing else. Many candidates assumed it was necessary to add a vertex when this was not the case. 

Part (b) was not found to be beyond many candidates if they used the inequality e \leqslant 3v - 6

Syllabus sections

Topic 10 - Option: Discrete mathematics » 10.7 » Euler’s relation: v - e + f = 2 ; theorems for planar graphs including e \leqslant 3v - 6 , e \leqslant 2v - 4 , leading to the results that {\kappa _5} and {\kappa _{3,3}} are not planar.

View options