Practise › Questions › Graphs: order, Eulerian paths and planarity
Graphs: order, Eulerian paths and planarity questions
The vocabulary the rest of the paper runs on, plus one theorem worth its weight: counting odd nodes settles whether a network can be walked without repeating an edge.
7 original questions · 24 marks · the graphs: order, eulerian paths and planarity notes · Decision Mathematics 1
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Explain why the number of odd nodes in any graph must be even.
Worked answer
Every edge contributes one to the order of each of its two ends, so the orders of all the nodes total twice the number of edges, which is even. The even-order nodes contribute an even amount, so the odd-order ones must too, and that is only possible if there is an even number of them. B1 for the orders totalling twice the edges, B1 for the deduction.A connected graph has nine edges and node orders 3, 3, 4, 3, 3 and 2. Verify the orders and classify the graph.
Worked answer
The orders total 18, which is twice the nine edges, as required. Four nodes are odd, and four is more than two, so the graph is neither Eulerian nor semi-Eulerian: no trail can use every edge exactly once. B1 for the total of 18, B1 for four odd nodes, B1 for the classification.State how many edges the complete graphs K5 and K6 have, and explain which of them is Eulerian.
Worked answer
Kn has n(n − 1)/2 edges, so K5 has 10 and K6 has 15. In Kn every node has order n − 1. For K5 that is 4, even, so K5 is Eulerian. For K6 it is 5, odd, and all six nodes are odd, so K6 is neither Eulerian nor semi-Eulerian. B1 B1 for the two edge counts, M1 for the order n − 1, A1 for the classification of each.Describe the planarity algorithm and explain what it does when the graph is not planar.
Worked answer
It needs a Hamiltonian cycle, one visiting every node exactly once. Redraw that cycle as a circle with the remaining edges as chords, then take the chords in turn, placing each inside or outside the circle so that it crosses nothing already placed. If every chord can be placed the graph is planar and the drawing proves it. If some chord conflicts with what is inside and also with what is outside, no placement exists and the graph is not planar. B1 for the Hamiltonian cycle, B1 for redrawing it as a circle with chords, B1 for placing each chord inside or outside, B1 for the conflicting chord.Two graphs both have six nodes, nine edges and the same list of node orders. Explain why that does not prove they are isomorphic.
Worked answer
Isomorphism requires a one-to-one correspondence of nodes that preserves every edge, and matching totals do not supply one. The orders could be arranged differently: in one graph the two order-4 nodes might be joined and in the other not. To prove isomorphism you must give the correspondence explicitly and check every edge. B1 for matching totals not supplying a correspondence, B1 for what a proof requires.In a network of paths through a park, exactly two junctions have an odd number of paths meeting at them. State what this means for a warden who must walk every path exactly once, and what changes if an extra path is built between those two junctions.
Worked answer
Two odd nodes makes the network semi-Eulerian. A trail using every path exactly once exists, but it must start at one odd junction and finish at the other, so the warden cannot end where they began. Building a path between the two odd junctions raises both orders by one. Every node is then even, the network is Eulerian, and a closed round exists: one extra path walked, but a return to the start. B1 for semi-Eulerian, B1 for the start and finish at the odd junctions, B1 for the network becoming Eulerian.K5 is the complete graph on the five nodes A, B, C, D and E. Taking ABCDEA as the Hamiltonian cycle, apply the planarity algorithm to K5 and hence prove that it is not planar.
Worked answer
K5 has 5 × 4/2 = 10 edges, and the cycle ABCDEA uses five of them. Redraw that cycle as a circle. The five edges left over become the chords AC, AD, BD, BE and CE.
Two chords clash when their ends interleave round the circle, so that drawing both on the same side would force a crossing. Chords sharing an end never clash. Working through the pairs: AC clashes with BD and BE; AD clashes with BE and CE; BD clashes with CE. That is five clashes, and every chord is in exactly two of them.
Follow them round: AC clashes with BD, BD with CE, CE with AD, AD with BE, and BE back with AC. The clashes form a single cycle of length five.
Placing the chords is the same as colouring that cycle with two colours, inside and outside, so that no clashing pair shares a colour. Go round the five-cycle alternating: the colours must alternate at every step, but after an odd number of steps you arrive back at the start needing the opposite colour to the one it already has. No such split exists, so whichever way the first four chords are placed, the fifth clashes with something inside and with something outside. K5 is therefore not planar.
The argument needs the odd length. A clash cycle of even length alternates back to itself consistently and the graph would be planar, so quoting 'the chords clash' without counting them proves nothing.
B1 for the five chords, M1 A1 for the clashes, M1 for the clash cycle of length five, M1 A1 for the two-colouring argument.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise graphs: order, eulerian paths and planarity one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.