Questions on graphs: order, Eulerian paths and planarity

Question 1

Explain why the number of odd nodes in any graph must be even.

Accepted 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.

Question 2

A connected graph has nine edges and node orders 3, 3, 4, 3, 3 and 2. Verify the orders and classify the graph.

Accepted 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.

Question 3

State Ore's condition for a graph on n nodes, and state what follows about a graph that fails it.

Accepted Answer

For a simple graph with n ≥ 3 nodes: if every pair of nodes that are not joined by an edge has orders totalling at least n, the graph is Hamiltonian. B1.
Nothing follows from a failure. The condition is sufficient and not necessary, so a graph that fails it may still be Hamiltonian and has to be examined directly. B1.
Only the unjoined pairs are tested. A pair already joined by an edge is not part of the condition at all, and including such pairs makes the test appear to pass or fail on evidence it does not use.

Question 4

K_3,3 is the complete bipartite graph in which each of three nodes is joined to each of three others and to nothing else. Write down its number of edges and the order of every node, and classify it as Eulerian, semi-Eulerian or neither.

Accepted Answer

Each of the three nodes on one side is joined to all three on the other, so there are 3 × 3 = 9 edges. B1. Every node is joined to the three on the other side and to nothing else, so every order is 3. B1. The orders total 6 × 3 = 18 = 2 × 9, as they must.
All six nodes are odd, and six is more than two, so K_3,3 is neither Eulerian nor semi-Eulerian. B1.

Question 5

State how many edges the complete graphs K5 and K6 have, and explain which of them is Eulerian.

Accepted Answer

K_n has n(n − 1)/2 edges, so K5 has 10 and K6 has 15. In K_n 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.

Question 6

Describe the planarity algorithm and explain what it does when the graph is not planar.

Accepted 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.

Question 7

Two graphs both have six nodes, nine edges and the same list of node orders. Explain why that does not prove they are isomorphic.

Accepted 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.

Question 8

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.

Accepted 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.

Question 9

A simple graph has nodes P, Q, R, S, T, U and edges PQ, PR, QR, QS, RS, RT, ST, SU, TU. Test it against Ore's condition, and find a Hamiltonian cycle.

Accepted Answer

Orders: P 2, Q 3, R 4, S 4, T 3, U 2, totalling 18 = 2 × 9, which matches the nine edges. B1.
The unjoined pairs are PS, PT, PU, QT, QU and RU, and n = 6, so each pair's orders must total at least 6. PS gives 2 + 4 = 6 and QT gives 3 + 3 = 6 and RU gives 4 + 2 = 6, all acceptable, but PT gives 2 + 3 = 5, PU gives 2 + 2 = 4 and QU gives 3 + 2 = 5. M1 for adding the orders of unjoined pairs, A1 for a pair falling short, so Ore's condition fails.
The graph is Hamiltonian all the same: P, Q, S, U, T, R, P uses PQ, QS, SU, UT, TR and RP and visits every node exactly once. B1.

Question 10

A graph has nodes P, Q, R, S, T, U and edges PS, PT, QS, QU, RT and RU. Colour it with two colours to show that it is bipartite, and write down the number of edges of its complement and the order of every node in the complement.

Accepted Answer

Colour P, Q and R one colour and S, T and U the other. Every one of the six edges joins a node of the first set to a node of the second, and no edge joins two nodes of the same colour, so the graph is bipartite with parts {P, Q, R} and {S, T, U}. M1 for a two-colouring, A1 for the two sets.
The complete graph on six nodes has 6 × 5 ÷ 2 = 15 edges, so the complement has 15 − 6 = 9 edges. B1. Every node has order 2 here, and a node is joined to 5 others in the complete graph, so every node of the complement has order 5 − 2 = 3. B1.
The graph is the six-cycle P, S, Q, U, R, T, P, and a cycle of even length is always bipartite: walk round it colouring alternately and the colours agree when the walk closes. A cycle of odd length is the case where they do not.

Question 11

A graph has nodes P, Q, R, S and edges PQ, QR, RS, SP and PR. The edge PR is subdivided by a new node W. Separately, in the original graph the edge QR is contracted. For each of the two new graphs, write down the number of nodes, the number of edges and the order of every node, naming the contracted node in bracket notation.

Accepted Answer

The original has 4 nodes, 5 edges and orders P 3, Q 2, R 3, S 2.
Subdividing PR puts W in the middle of that edge, so PR is replaced by PW and WR. The graph has 5 nodes and 6 edges, with orders P 3, Q 2, R 3, S 2 and W 2. B1 for the counts, B1 for the orders.
Contracting QR pulls Q and R together into a single node written (QR). The edge QR itself disappears; PQ and PR both become edges from P to (QR) and count once between them; RS becomes (QR)S; SP is untouched. The result has 3 nodes and 3 edges: the triangle P, (QR), S, with every order 2. M1 for the contraction, A1 for the triangle.
Subdividing changes neither the number of independent cycles nor whether the graph can be drawn without crossings, since it only puts a node in the middle of an existing line. Contracting can change both.

Question 12

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.

Accepted 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.

Question 13

K5 is the complete graph on the five nodes A, B, C, D and E, and it is not planar. Split its edges into two sets, each of which can be drawn without crossings, and hence write down the thickness of K5.

Accepted Answer

K5 has 5 × 4 ÷ 2 = 10 edges. Since K5 is not planar, no single drawing carries all ten without a crossing, so the thickness is at least 2. B1.
Take the first layer to be the cycle AB, BC, CD, DE, EA, which is a pentagon and so plainly planar. M1 for a split into two sets, A1 for this layer.
The five edges left over are AC, CE, EB, BD and DA, and following them in that order returns to A: they form the five-cycle A, C, E, B, D, A, which is again a pentagon and again planar. A1 for the second layer.
Two planar layers suffice and one does not, so the thickness of K5 is 2. A1.

Question 14

K_3,3 has nodes P, Q, R on one side and S, T, U on the other, with every node of one side joined to every node of the other. Taking P, S, Q, T, R, U, P as the Hamiltonian cycle, apply the planarity algorithm and hence prove that K_3,3 is not planar.

Accepted Answer

K_3,3 has 3 × 3 = 9 edges, and the cycle uses PS, SQ, QT, TR, RU and UP, which is six of them. Redraw that cycle as a circle with P, S, Q, T, R, U round it in order. The three edges left over become the chords PT, QU and RS. B1.
Two chords clash when their ends interleave round the circle, so that drawing both on the same side forces a crossing. Between P and T, going the short way, lie S and Q. QU has Q there and U on the far arc, so PT clashes with QU; RS has S there and R on the far arc, so PT clashes with RS. Between Q and U lie T and R, and RS has R there and S on the far arc, so QU clashes with RS. M1 for testing the pairs, A1 for all three pairs clashing.
Every chord therefore clashes with both of the others. Placing them needs three regions, one for each, but the circle offers only inside and outside: whichever two are placed, they lie on opposite sides and the third clashes with both. M1 for two regions being too few for three mutually clashing chords, A1 for the conclusion that K_3,3 is not planar.

Question 15

Euler's formula says that a connected planar graph drawn without crossings satisfies n − m + f = 2, where n is the number of nodes, m the number of edges and f the number of regions, the region outside the drawing included. Show that a simple connected planar graph with n ≥ 3 satisfies m ≤ 3n − 6, and apply the inequality to K5 and to K_3,3, which have 10 and 9 edges respectively.

Accepted Answer

In a simple graph with at least three nodes, every region is bounded by at least three edges, since two edges cannot enclose a region without one of them being repeated. M1. Each edge lies on the boundary of at most two regions, so counting edge-and-region pairs both ways gives 3f ≤ 2m. M1.
Euler's formula gives f = 2 − n + m, so 3(2 − n + m) ≤ 2m, that is 6 − 3n + 3m ≤ 2m, which rearranges to m ≤ 3n − 6. A1.
K5 has n = 5 and m = 10, while 3n − 6 = 9. Since 10 > 9 the inequality fails, so K5 cannot be planar. B1.
K_3,3 has n = 6 and m = 9, while 3n − 6 = 12. Since 9 ≤ 12 the inequality holds, and a graph that passes may or may not be planar: the inequality settles nothing about K_3,3. M1 for the substitution, A1 for the test being inconclusive.
K_3,3 contains no triangle, so every region there needs at least four edges and the sharper bound m ≤ 2n − 4 = 8 applies, which 9 does break; the planarity algorithm settles it without any counting at all.