Planar graphs, Hamiltonian cycles, the planarity algorithm step by step.
12 original questions, 69 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.
Write down a Hamiltonian cycle for G, starting and finishing at A.
4 marks
Show answer
a) A graph that can be drawn in a plane so that no two arcs meet (cross) except at a vertexb) A cycle (closed path) that passes through every vertex exactly once and returns to the start vertexc) e.g. A B C F E D A
2
The graph below has four vertices and six arcs. In the drawing, arcs AC and BD cross.
Taking ABCDA as the Hamiltonian cycle, use the planarity algorithm to show that the graph is planar. Draw the graph without any arcs crossing.
3 marks
Show answer
AC inside, BD outside: planar
3
The graph below has six vertices, A to F.
Taking ABCDEFA as the Hamiltonian cycle, use the planarity algorithm to determine whether the graph is planar. You must make your working clear and justify your answer.
4 marks
Show answer
Planar: AC, CE, AE inside; BD, BF outside
4
The graph below has seven vertices, A to G, and thirteen arcs.
Starting at A, find a Hamiltonian cycle for the graph.
Use your Hamiltonian cycle and the planarity algorithm to determine whether the graph is planar. You must make your working clear and justify your answer.
5 marks
Show answer
a) e.g. A B C D E F G Ab) Planar: AC, AE, CE inside; BG, DF, DG outside
5
Three new houses, A, B and C, are each to be connected by an underground pipe to each of three supply points: water X, gas Y and a heat pump Z. The pipes must all be laid at the same depth, so no two pipes may cross. The graph below shows the nine connections.
Write down a Hamiltonian cycle for the graph, starting at A.
Use the planarity algorithm to determine whether the pipes can be laid without crossing. You must make your working clear.
5 marks
Show answer
a) e.g. A X B Y C Z Ab) Not planar: AY inside, BZ and CX outside, but BZ and CX cross; the pipes cannot be laid without a crossing
6
A graph G has six vertices, A to F. The vertices adjacent to each vertex are listed below.
Vertex
Adjacent to
A
B, C, D, F
B
A, C, D, F
C
A, B, D, E
D
A, B, C, E, F
E
C, D, F
F
A, B, D, E
State the number of arcs in G.
Taking ABCDEFA as the Hamiltonian cycle, which is drawn below, use the planarity algorithm to determine whether G is planar. You must make your working clear and justify your answer.
5 marks
Show answer
a) 12b) Not planar: AC I, BD O, BF O, CE I, AD I, but AD and CE both inside and they cross
7
The graph below has ten vertices and thirteen arcs. A Hamiltonian cycle for the graph begins C, X, A, V, ...
Complete the Hamiltonian cycle.
Hence use the planarity algorithm to determine whether the graph is planar. You must make your working clear and justify your answer.
5 marks
Show answer
a) C X A V D Y E Z B W Cb) Not planar
8
The graph below shows the footpaths, drawn as arcs, between six picnic areas, A to F, in a park.
Taking ABCDEFA as the Hamiltonian cycle, use the planarity algorithm to show that the graph is planar.
A new footpath AD is to be added. Determine whether the graph remains planar. You must make your working clear.
7 marks
Show answer
a) Planar: BD, BE, AE inside; CF outsideb) Not planar: AE I, CF O, BD I, BE I, AD I, then AD crosses BE with both inside
9
The graph G below has five vertices and seven arcs.
State the number of arcs in the complete graph Kn, in terms of n.
Find the number of arcs that would need to be added to G to make the complete graph K5, and list them.
Taking ABCDEA as the Hamiltonian cycle, which is drawn on the right below, use the planarity algorithm to show that K5 is not planar.
6 marks
Show answer
a) n(n - 1)/2b) 3: AD, BD and CEc) AC I, BD O, BE O, CE I, AD I but AD crosses CE, both inside: not planar
10
A circuit board has seven components, A to G. The graph below shows the thirteen copper tracks that must join pairs of components. Tracks printed on one side of the board must not cross.
Show that A B C D E F G A is a Hamiltonian cycle for the graph.
Use the planarity algorithm to determine whether all thirteen tracks can be printed on one side of the board.
The designer moves one track to the other side of the board. Find a track that could be moved so that the remaining twelve tracks can be printed on one side without crossing. Justify your answer.
8 marks
Show answer
a) AB, BC, CD, DE, EF, FG and GA are all arcs and each vertex is visited onceb) Not planar, so the tracks cannot all be printed on one sidec) e.g. AD: the algorithm then gives a valid labelling (other answers: BF, CG)
11
The graph below has seven vertices, A to G, and twelve arcs. A B C D E F G A is a Hamiltonian cycle for the graph.
Use the planarity algorithm to show that the graph is planar.
One more arc is to be added to the graph. It will be one of AE, AF or CF. Determine which of these arcs could be added so that the graph is still planar. You must justify your answer.
7 marks
Show answer
a) Planar: BE, BF, CE inside; AD, DG outsideb) AF only: it crosses only an outside arc so can go inside, while AE and CF each cross an inside arc and an outside arc
12
The graph G below has six vertices, A to F, and ten arcs.
State whether G is Eulerian, semi-Eulerian or neither, giving a reason for your answer.
Find the number of arcs that would need to be added to G to make the complete graph K6.
Write down a Hamiltonian cycle for G, starting at A.
Use your Hamiltonian cycle and the planarity algorithm to show that G is planar.
The arc BD is added to G. State, with a reason, whether the new graph is Eulerian, and determine whether it is planar.
10 marks
Show answer
a) Semi-Eulerian: exactly two vertices (B and D) have odd degreeb) 5c) A B C D E F Ad) Planar: AC, AD inside; BE, CE outsidee) Eulerian, since every vertex now has even degree; not planar
Your score
Answer the questions above and your score appears here.
Every question here is original and written by Robinson Tuition. It follows the Edexcel A-level Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.