Marks available | 2 |
Reference code | 15M.1.hl.TZ0.4 |
Question
A simple graph \(G\) is represented by the following adjacency table.
Draw the simple graph \(G\).
Explain why \(G\) does not contain an Eulerian circuit.
Show that \(G\) has a Hamiltonian cycle.
State whether or not \(G\) is planar, giving a reason for your answer.
State whether or not the simple graph \(G\) is bipartite, giving a reason for your answer.
Draw the complement \(G’\) of \(G\).
Markscheme
A1
because it has vertices which are not of even degree. A1
for example \({\text{D}} \to {\text{C}} \to {\text{B}} \to {\text{E}} \to {\text{A}} \to {\text{F}} \to {\text{D}}\) A2
\(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\)
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
A2
Note: Award A1 if extra line seen or missed out.
Examiners report
This question was very well answered in general.
This question was very well answered in general.
This question was very well answered in general.
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.
This question was very well answered in general.
This question was very well answered in general.
Marks available | 3 |
Reference code | 17M.1.hl.TZ0.11 |
Question
The simple connected planar graph \(J\) has the following adjacency table.
Without attempting to draw \(J\), verify that J satisfies the handshaking lemma;
Without attempting to draw \(J\), determine the number of faces in \(J\).
The vertices D and G are joined by a single edge to form the graph \(K\). Show that \(K\) is not planar.
Explain why a graph containing a cycle of length three cannot be bipartite.
Hence by finding a cycle of length three, show that the complement of \(K\) is not bipartite.
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]
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]
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]
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]
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]