Further Maths Route inspection Practice Questions

Write down the degree of every vertex

The degree of a vertex is the number of arcs that 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.

State how many vertices have odd degree

This number is even, as the handshaking lemma requires.

Write down the degree of every vertex

The degree of a vertex is the number of arcs that 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.

Select the vertices whose degree is odd

A vertex is odd when an odd number of arcs meet at it; there are 4 such vertices here.

Write down the degree of every vertex

The degree of a vertex is the number of arcs that 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.

Check the handshaking lemma

The degrees add up to twice the number of arcs, so the number of odd vertices must be even.

Count the vertices and the arcs of the network

The network is connected, so a route inspection solution exists.

Recall the route inspection algorithm

Every arc is walked at least once; only the arcs on the chosen shortest paths are walked twice.

State the conclusion about traversability

A connected network is traversable exactly when it has no odd vertices (closed route) or exactly two (open route).

Write down the degree of every vertex

The degree of a vertex is the number of arcs that 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 $G$

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

Option 2: start at $D$ 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 $D$

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 $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 $D$ and finish at $G$

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 $G$

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 $G$, so those two odd vertices need no repeated arc.

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