Route inspection Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Route inspection questions. See exactly how to solve problems on odd-vertices, degrees, handshaking, route-inspection.

odd-verticesdegreeshandshakingroute-inspectionchinese-postmanpairing-odd-vertices
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
A network of roads has junctions AA, BB, CC, DD and EE. The roads of the network and their lengths, in km, are AB=12AB=12, AC=5AC=5, AE=8AE=8, BD=9BD=9, BE=6BE=6, CD=15CD=15, DE=11DE=11. State the number of vertices of odd degree in this network.

Worked solution

  1. Write down the degree of every vertex

    deg⁡(A)=3,  deg⁡(B)=3,  deg⁡(C)=2,  deg⁡(D)=3,  deg⁡(E)=3\deg(A)=3,\;\deg(B)=3,\;\deg(C)=2,\;\deg(D)=3,\;\deg(E)=3

    The degree of a vertex is the number of arcs that meet at it.

  2. Pick out the vertices of odd degree

    odd vertices:  A,  B,  D,  E\text{odd vertices}:\;A,\;B,\;D,\;E

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

  3. State how many vertices have odd degree

    number of odd vertices=4\text{number of odd vertices}=4

    This number is even, as the handshaking lemma requires.

Answer
44
Question 2
2 markseasy
A network of roads has junctions AA, BB, CC, DD and EE. The roads of the network and their lengths, in km, are AB=15AB=15, AC=3AC=3, AD=13AD=13, BC=9BC=9, BD=5BD=5, CE=11CE=11, DE=8DE=8. State the number of vertices of odd degree in this network.

Worked solution

  1. Write down the degree of every vertex

    deg⁡(A)=3,  deg⁡(B)=3,  deg⁡(C)=3,  deg⁡(D)=3,  deg⁡(E)=2\deg(A)=3,\;\deg(B)=3,\;\deg(C)=3,\;\deg(D)=3,\;\deg(E)=2

    The degree of a vertex is the number of arcs that meet at it.

  2. Pick out the vertices of odd degree

    odd vertices:  A,  B,  C,  D\text{odd vertices}:\;A,\;B,\;C,\;D

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

  3. State how many vertices have odd degree

    number of odd vertices=4\text{number of odd vertices}=4

    This number is even, as the handshaking lemma requires.

Answer
44
Question 3
2 markseasy
A network of roads has junctions AA, BB, CC, DD and EE. The roads of the network and their lengths, in km, are AB=17AB=17, AC=16AC=16, AE=14AE=14, BC=10BC=10, BD=24BD=24, BE=23BE=23, DE=3DE=3. State the number of vertices of odd degree in this network.

Worked solution

  1. Write down the degree of every vertex

    deg⁡(A)=3,  deg⁡(B)=4,  deg⁡(C)=2,  deg⁡(D)=2,  deg⁡(E)=3\deg(A)=3,\;\deg(B)=4,\;\deg(C)=2,\;\deg(D)=2,\;\deg(E)=3

    The degree of a vertex is the number of arcs that meet at it.

  2. Pick out the vertices of odd degree

    odd vertices:  A,  E\text{odd vertices}:\;A,\;E

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

  3. State how many vertices have odd degree

    number of odd vertices=2\text{number of odd vertices}=2

    This number is even, as the handshaking lemma requires.

Answer
22
Question 4
2 markseasy
A network of roads has junctions AA, BB, CC, DD and EE. The roads of the network and their lengths, in km, are AB=11AB=11, AC=17AC=17, AD=24AD=24, AE=25AE=25, BC=3BC=3, BD=7BD=7, BE=17BE=17. State the number of vertices of odd degree in this network.

Worked solution

  1. Write down the degree of every vertex

    deg⁡(A)=4,  deg⁡(B)=4,  deg⁡(C)=2,  deg⁡(D)=2,  deg⁡(E)=2\deg(A)=4,\;\deg(B)=4,\;\deg(C)=2,\;\deg(D)=2,\;\deg(E)=2

    The degree of a vertex is the number of arcs that meet at it.

  2. Pick out the vertices of odd degree

    odd vertices:  none\text{odd vertices}:\;\text{none}

    Every vertex has even degree, so the network is Eulerian.

  3. State how many vertices have odd degree

    number of odd vertices=0\text{number of odd vertices}=0

    This number is even, as the handshaking lemma requires.

Answer
00
Question 5
2 markseasy
A network of roads has junctions AA, BB, CC, DD and EE. The roads of the network and their lengths, in km, are AB=7AB=7, AC=11AC=11, AE=8AE=8, BC=17BC=17, BD=5BD=5, CD=8CD=8, DE=12DE=12. Find the sum of the weights of all the arcs in this network.

Worked solution

  1. List the weights of all the arcs

    AB=7,  AC=11,  AE=8,  BC=17,  BD=5,  CD=8,  DE=12AB=7,\;AC=11,\;AE=8,\;BC=17,\;BD=5,\;CD=8,\;DE=12

    The network has 7 arcs.

  2. Check the handshaking lemma

    ∑vdeg⁡(v)=3+3+3+3+2=14=2×7\sum_{v}\deg(v)=3+3+3+3+2=14=2\times7

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

  3. Add the weights of all the arcs in the network

    7+11+8+17+5+8+12=687+11+8+17+5+8+12=68

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

Answer
6868

Unlock 65 more Route inspection questions

Create a free account to work through every Further Maths Route inspection question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Route inspection practice

Hard QuestionsPractice Questions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks