IB DP Further Mathematics 6.8 HL Paper 1

Marks available2
Reference code15M.1.hl.TZ0.4

Question

A simple graph \(G\) is represented by the following adjacency table.

Draw the simple graph \(G\).

[1]
a.

Explain why \(G\) does not contain an Eulerian circuit.

[1]
b.

Show that \(G\) has a Hamiltonian cycle.

[2]
c.

State whether or not \(G\) is planar, giving a reason for your answer.

[2]
d.

State whether or not the simple graph \(G\) is bipartite, giving a reason for your answer.

[2]
e.

Draw the complement \(G’\) of \(G\).

[2]
f.

Markscheme

     A1

a.

because it has vertices which are not of even degree.     A1

b.

for example \({\text{D}} \to {\text{C}} \to {\text{B}} \to {\text{E}} \to {\text{A}} \to {\text{F}} \to {\text{D}}\)     A2

c.

\(G\) is planar.     A1

either note from original graph in part (a) that there are no edges crossing or a redrawing with statement that there are no edges crossing.     R1

Note: Do not accept an argument based on \(e \leqslant 3v – 6\)

d.

the graph is not bipartite.     A1

EITHER

the graph contains a triangle     R1

OR

to be bipartite according to line 1 of the table A, C and D need to be one set as A connects to B, E and F. Since C and D are connected, this is contradicted.     R1

e.

     A2

Note: Award A1 if extra line seen or missed out.

f.

Examiners report

This question was very well answered in general.

a.

This question was very well answered in general.

b.

This question was very well answered in general.

c.

This question was very well answered in general. In (d), some candidates stated that G is planar because \(e \leqslant 3v – 6\). It is however important to realise that this condition is necessary for a graph to be planar but not sufficient. Some candidates stated that G is planar ‘because I have drawn it as a planar graph’ or even ‘see graph in (a)’. Candidates were expected to state that G is planar because it can be drawn with no edges crossing.

d.

This question was very well answered in general.

e.

This question was very well answered in general.

f.
Marks available3
Reference code17M.1.hl.TZ0.11

Question

The simple connected planar graph \(J\) has the following adjacency table.

M17/5/FURMA/HP1/ENG/TZ0/11

Without attempting to draw \(J\), verify that J satisfies the handshaking lemma;

[1]
a.i.

Without attempting to draw \(J\), determine the number of faces in \(J\).

[3]
a.ii.

The vertices D and G are joined by a single edge to form the graph \(K\). Show that \(K\) is not planar.

[3]
b.

Explain why a graph containing a cycle of length three cannot be bipartite. 

[3]
c.i.

Hence by finding a cycle of length three, show that the complement of \(K\) is not bipartite.

[2]
c.ii.

Markscheme

the sum of degrees of the vertices is even (36) or the sum of degrees of the vertices is twice the number of edges A1

[2 marks]

a.i.

the number of edges \((e)\) is 18     A1

using Euler’s relation \(v – e + f = 2\)     M1

\(f = 2 + 18 – 8 = 12\)     A1

[2 marks]

a.ii.

if \(K\) is planar then \(e \leqslant 3v – 6\)     M1

\(v = 8\) and \(e = 19\)     A1

the inequality is not satisfied so \(K\) is not planar     A1AG

[3 marks]

b.

let PQRP be a cycle of length 3 in a graph     M1

Note:     Accept a diagram instead of this statement.

suppose the graph is bipartite

then P must belong to one of the two disjoint sets of vertices and Q, R must belong to the other disjoint set     R1

but Q, R cannot belong to the same set because they are linked     R1

therefore the graph cannot be bipartite     AG

[??? marks]

c.i.

for example, a suitable cycle of order 3 is AFHA     (M1)A1

Note:     Award M1 for a valid attempt at drawing the complement or constructing its adjacency table.

[??? marks]

c.ii.

Examiners report

[N/A]
a.i.
[N/A]
a.ii.
[N/A]
b.
[N/A]
c.i.
[N/A]
c.ii.
Scroll to Top