Hard Further Maths Route inspection Questions

Find the degree of vertex $A$

Vertex $A$ lies on the arcs $AB$, $AC$, so 2 arcs meet at it.

Find the degree of vertex $B$

Vertex $B$ lies on the arcs $AB$, $BC$, $BD$, $BG$, $BH$, so 5 arcs meet at it.

Find the degree of vertex $C$

Vertex $C$ lies on the arcs $AC$, $BC$, $CD$, $CF$, $CH$, so 5 arcs meet at it.

Find the degree of vertex $D$

Vertex $D$ lies on the arcs $BD$, $CD$, $DE$, $DG$, $DH$, so 5 arcs meet at it.

Find the degree of vertex $E$

Vertex $E$ lies on the arcs $DE$, $EF$, so 2 arcs meet at it.

Find the degree of vertex $F$

Vertex $F$ lies on the arcs $CF$, $EF$, so 2 arcs meet at it.

Find the degree of vertex $G$

Vertex $G$ lies on the arcs $BG$, $DG$, so 2 arcs meet at it.

Find the degree of vertex $H$

Vertex $H$ lies on the arcs $BH$, $CH$, $DH$, so 3 arcs meet at it.

Pick out the vertices of odd degree

There are 4 vertices of odd degree; by the handshaking lemma this number is always even.

Add the weights of all the arcs in the network

Every arc must be traversed at least once, so this total is the irreducible part of any route.

Pairing 1: pair the odd vertices as BC and DH

Each term is the length of the shortest path between the two vertices of that pair, not necessarily the direct arc.

Pairing 2: pair the odd vertices as BH and CD

Each term is the length of the shortest path between the two vertices of that pair, not necessarily the direct arc.

Pairing 3: pair the odd vertices as BD and CH

Each term is the length of the shortest path between the two vertices of that pair, not necessarily the direct arc.

Choose the pairing with the smallest total

This pairing is strictly cheaper than every other pairing, so the repeated route is unique.

Write down the arcs that are actually repeated

The repeated arcs are the arcs lying on the shortest paths joining the paired odd vertices.

Select the total length of the shortest closed route

Using the direct arc instead of the shortest path between a paired vertex would have given the wrong total of $231$.

Find the degree of vertex $A$

Vertex $A$ lies on the arcs $AB$, $AC$, $AE$, $AF$, $AG$, so 5 arcs meet at it.

Find the degree of vertex $B$

Vertex $B$ lies on the arcs $AB$, $BD$, $BF$, $BG$, so 4 arcs meet at it.

Find the degree of vertex $C$

Vertex $C$ lies on the arcs $AC$, $CE$, $CF$, $CH$, so 4 arcs meet at it.

Find the degree of vertex $D$

Vertex $D$ lies on the arcs $BD$, $DH$, so 2 arcs meet at it.

Find the degree of vertex $E$

Vertex $E$ lies on the arcs $AE$, $CE$, so 2 arcs meet at it.

Find the degree of vertex $F$

Vertex $F$ lies on the arcs $AF$, $BF$, $CF$, so 3 arcs meet at it.

Find the degree of vertex $G$

Vertex $G$ lies on the arcs $AG$, $BG$, $GH$, so 3 arcs meet at it.

Find the degree of vertex $H$

Vertex $H$ lies on the arcs $CH$, $DH$, $GH$, so 3 arcs meet at it.

Pick out the vertices of odd degree

There are 4 vertices of odd degree; by the handshaking lemma this number is always even.

Add the weights of all the arcs in the network

Every arc must be traversed at least once, so this total is the irreducible part of any route.

Pairing 1: pair the odd vertices as AF and GH

Each term is the length of the shortest path between the two vertices of that pair, not necessarily the direct arc.

Pairing 2: pair the odd vertices as AG and FH

Each term is the length of the shortest path between the two vertices of that pair, not necessarily the direct arc.

Pairing 3: pair the odd vertices as AH and FG

Each term is the length of the shortest path between the two vertices of that pair, not necessarily the direct arc.

Choose the pairing with the smallest total

This pairing is strictly cheaper than every other pairing, so the repeated route is unique.

Write down the arcs that are actually repeated

The repeated arcs are the arcs lying on the shortest paths joining the paired odd vertices.

Select the total length of the shortest closed route

Using the direct arc instead of the shortest path between a paired vertex would have given the wrong total of $267$.

Find the degree of vertex $A$

Vertex $A$ lies on the arcs $AB$, $AE$, $AG$, so 3 arcs meet at it.

Find the degree of vertex $B$

Vertex $B$ lies on the arcs $AB$, $BC$, $BD$, $BE$, $BG$, so 5 arcs meet at it.

Find the degree of vertex $C$

Vertex $C$ lies on the arcs $BC$, $CD$, so 2 arcs meet at it.

Find the degree of vertex $D$

Vertex $D$ lies on the arcs $BD$, $CD$, $DG$, $DH$, so 4 arcs meet at it.

Find the degree of vertex $E$

Vertex $E$ lies on the arcs $AE$, $BE$, $EF$, so 3 arcs meet at it.

Find the degree of vertex $F$

Vertex $F$ lies on the arcs $EF$, $FG$, $FH$, so 3 arcs meet at it.

Find the degree of vertex $G$

Vertex $G$ lies on the arcs $AG$, $BG$, $DG$, $FG$, so 4 arcs meet at it.

Find the degree of vertex $H$

Vertex $H$ lies on the arcs $DH$, $FH$, so 2 arcs meet at it.

Pick out the vertices of odd degree

There are 4 vertices of odd degree; by the handshaking lemma this number is always even.

Add the weights of all the arcs in the network

Every arc must be traversed at least once, so this total is the irreducible part of any route.

Option 1: start at $B$ and finish at $F$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 2: start at $E$ and finish at $F$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 3: start at $A$ and finish at $F$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 4: start at $A$ and finish at $B$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 5: start at $B$ and finish at $E$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 6: start at $A$ and finish at $E$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Select the start and finish that minimise the repeated length

The two odd vertices left unpaired are the ones whose pairing would have been most expensive to repeat.

Find the degree of vertex $A$

Vertex $A$ lies on the arcs $AB$, $AC$, $AG$, $AH$, so 4 arcs meet at it.

Find the degree of vertex $B$

Vertex $B$ lies on the arcs $AB$, $BC$, $BD$, so 3 arcs meet at it.

Find the degree of vertex $C$

Vertex $C$ lies on the arcs $AC$, $BC$, $CE$, $CH$, so 4 arcs meet at it.

Find the degree of vertex $D$

Vertex $D$ lies on the arcs $BD$, $DE$, $DF$, $DG$, $DH$, so 5 arcs meet at it.

Find the degree of vertex $E$

Vertex $E$ lies on the arcs $CE$, $DE$, $EF$, so 3 arcs meet at it.

Find the degree of vertex $F$

Vertex $F$ lies on the arcs $DF$, $EF$, so 2 arcs meet at it.

Find the degree of vertex $G$

Vertex $G$ lies on the arcs $AG$, $DG$, so 2 arcs meet at it.

Find the degree of vertex $H$

Vertex $H$ lies on the arcs $AH$, $CH$, $DH$, so 3 arcs meet at it.

Pick out the vertices of odd degree

There are 4 vertices of odd degree; by the handshaking lemma this number is always even.

Add the weights of all the arcs in the network

Every arc must be traversed at least once, so this total is the irreducible part of any route.

Option 1: start at $B$ and finish at $D$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 2: start at $B$ and finish at $E$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 3: start at $D$ and finish at $H$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 4: start at $D$ and finish at $E$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 5: start at $E$ and finish at $H$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 6: start at $B$ and finish at $H$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Choose the option with the smallest repeated length

Leaving these two odd vertices unpaired is strictly cheaper than every other choice.

Write down the arcs that are actually repeated

The repeated arcs are the arcs lying on the shortest paths joining the paired odd vertices.

Add the repeated length to the total weight of the network

The route starts at $B$ and finishes at $D$, so those two odd vertices need no repeated arc.

Find the degree of vertex $A$

Vertex $A$ lies on the arcs $AB$, $AD$, $AF$, so 3 arcs meet at it.

Find the degree of vertex $B$

Vertex $B$ lies on the arcs $AB$, $BC$, so 2 arcs meet at it.

Find the degree of vertex $C$

Vertex $C$ lies on the arcs $BC$, $CE$, $CG$, so 3 arcs meet at it.

Find the degree of vertex $D$

Vertex $D$ lies on the arcs $AD$, $DF$, $DG$, $DH$, so 4 arcs meet at it.

Find the degree of vertex $E$

Vertex $E$ lies on the arcs $CE$, $EF$, so 2 arcs meet at it.

Find the degree of vertex $F$

Vertex $F$ lies on the arcs $AF$, $DF$, $EF$, $FG$, $FH$, so 5 arcs meet at it.

Find the degree of vertex $G$

Vertex $G$ lies on the arcs $CG$, $DG$, $FG$, $GH$, so 4 arcs meet at it.

Find the degree of vertex $H$

Vertex $H$ lies on the arcs $DH$, $FH$, $GH$, so 3 arcs meet at it.

Pick out the vertices of odd degree

There are 4 vertices of odd degree; by the handshaking lemma this number is always even.

Add the weights of all the arcs in the network

Every arc must be traversed at least once, so this total is the irreducible part of any route.

Option 1: start at $A$ and finish at $C$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 2: start at $A$ and finish at $H$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 3: start at $C$ and finish at $H$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 4: start at $C$ and finish at $F$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 5: start at $A$ and finish at $F$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Option 6: start at $F$ and finish at $H$

The two unpaired odd vertices are the start and the finish; the remaining odd vertices must still be paired up.

Choose the option with the smallest repeated length

Leaving these two odd vertices unpaired is strictly cheaper than every other choice.

Write down the arcs that are actually repeated

The repeated arcs are the arcs lying on the shortest paths joining the paired odd vertices.

Add the repeated length to the total weight of the network

The route starts at $A$ and finishes at $C$, so those two odd vertices need no repeated arc.