Hard Further Maths Graphs and networks Questions

Challenging, exam-style Further Maths Graphs and networks questions with worked solutions. Stretch yourself on the hardest adjacency-matrix, walks, matrix-powers, closed-walks problems.

adjacency-matrixwalksmatrix-powersclosed-walksdigraphnetworks
Further Maths34 questionsStep-by-step solutions
Question 1
9 markschallenging
The graph GG has vertex set V={A,B,C,D,E,F,G}V=\{A,B,C,D,E,F,G\} and edge set E={AB,AC,AD,BC,BE,CF,DE,DF,EF,FG}E=\{AB,AC,AD,BC,BE,CF,DE,DF,EF,FG\}. Which of the following is the degree sequence of GG, written in descending order?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E,F,G},E={AB,AC,AD,BC,BE,CF,DE,DF,EF,FG}V=\{A,B,C,D,E,F,G\},\quad E=\{AB,AC,AD,BC,BE,CF,DE,DF,EF,FG\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

    ∣V∣=7,∣E∣=10|V|=7,\quad |E|=10

    The graph has 7 vertices and 10 edges.

  3. Work out the degree of every vertex

    deg⁡(A)=3,deg⁡(B)=3,deg⁡(C)=3,deg⁡(D)=3,deg⁡(E)=3,deg⁡(F)=4,deg⁡(G)=1\deg(A)=3,\quad \deg(B)=3,\quad \deg(C)=3,\quad \deg(D)=3,\quad \deg(E)=3,\quad \deg(F)=4,\quad \deg(G)=1

    For each vertex, count how many edges have that vertex as an endpoint.

  4. Find the degree of vertex AA

    A: AB,AC,AD ⇒ deg⁡(A)=3A:\ AB,AC,AD\ \Rightarrow\ \deg(A)=3

    AA is joined to BB, CC, DD. The degree (valency) of a vertex is the number of edges at it.

  5. Find the degree of vertex BB

    B: BA,BC,BE ⇒ deg⁡(B)=3B:\ BA,BC,BE\ \Rightarrow\ \deg(B)=3

    BB is joined to AA, CC, EE. The degree (valency) of a vertex is the number of edges at it.

  6. Find the degree of vertex CC

    C: CA,CB,CF ⇒ deg⁡(C)=3C:\ CA,CB,CF\ \Rightarrow\ \deg(C)=3

    CC is joined to AA, BB, FF. The degree (valency) of a vertex is the number of edges at it.

  7. Find the degree of vertex DD

    D: DA,DE,DF ⇒ deg⁡(D)=3D:\ DA,DE,DF\ \Rightarrow\ \deg(D)=3

    DD is joined to AA, EE, FF. The degree (valency) of a vertex is the number of edges at it.

  8. Find the degree of vertex EE

    E: EB,ED,EF ⇒ deg⁡(E)=3E:\ EB,ED,EF\ \Rightarrow\ \deg(E)=3

    EE is joined to BB, DD, FF. The degree (valency) of a vertex is the number of edges at it.

  9. Find the degree of vertex FF

    F: FC,FD,FE,FG ⇒ deg⁡(F)=4F:\ FC,FD,FE,FG\ \Rightarrow\ \deg(F)=4

    FF is joined to CC, DD, EE, GG. The degree (valency) of a vertex is the number of edges at it.

  10. Find the degree of vertex GG

    G: GF ⇒ deg⁡(G)=1G:\ GF\ \Rightarrow\ \deg(G)=1

    GG is joined to FF. The degree (valency) of a vertex is the number of edges at it.

  11. Add the degrees of all the vertices

    ∑v∈Vdeg⁡(v)=3+3+3+3+3+4+1=20\sum_{v\in V}\deg(v)=3+3+3+3+3+4+1=20

    The degree sum counts each edge twice, once at each end.

  12. Apply the handshaking lemma

    ∑v∈Vdeg⁡(v)=2∣E∣=2×10=20\sum_{v\in V}\deg(v)=2|E|=2\times 10=20

    Every edge contributes 11 to the degree of each of its two endpoints.

  13. List the vertices of odd degree

    odd: {A,B,C,D,E,G}(6 of them)\text{odd:}\ \{A,B,C,D,E,G\}\quad(6\text{ of them})

    The number of odd vertices is always even, by the handshaking lemma.

  14. Recall the handshaking lemma

    ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v\in V}\deg(v)=2|E|

    The degrees of all the vertices add up to twice the number of edges.

  15. Recall that the number of odd vertices is even

    #{v:deg⁡(v) odd}≡0(mod2)\#\{v:\deg(v)\text{ odd}\}\equiv 0\pmod 2

    This follows at once from the handshaking lemma.

  16. Write the degrees in descending order

    (4,3,3,3,3,3,1)\left(4,3,3,3,3,3,1\right)

    This list of degrees is the degree sequence of GG.

Answer
(4,3,3,3,3,3,1)\left(4,3,3,3,3,3,1\right)
Question 2
9 markschallenging
The network GG has vertex set V={A,B,C,D,E,F}V=\{A,B,C,D,E,F\} and weighted edge set E={AB:4,AC:7,BC:2,BD:9,CD:3,CE:6,DE:2,DF:8,EF:5}E=\{AB:4,AC:7,BC:2,BD:9,CD:3,CE:6,DE:2,DF:8,EF:5\}, where each number is the weight of that edge. Which of the following is the shortest route from AA to FF, together with its total weight?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E,F},E={AB:4,AC:7,BC:2,BD:9,CD:3,CE:6,DE:2,DF:8,EF:5}V=\{A,B,C,D,E,F\},\quad E=\{AB:4,AC:7,BC:2,BD:9,CD:3,CE:6,DE:2,DF:8,EF:5\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

    ∣V∣=6,∣E∣=9|V|=6,\quad |E|=9

    The graph has 6 vertices and 9 edges.

  3. Start Dijkstra's algorithm at AA

    d(A,A)=0d(A,A)=0

    The starting vertex takes the permanent label 00.

  4. Make the label at BB permanent

    d(A,B)=4d(A,B)=4

    The smallest temporary label can never be improved, so it becomes permanent.

  5. Make the label at CC permanent

    d(A,C)=6d(A,C)=6

    The smallest temporary label can never be improved, so it becomes permanent.

  6. Make the label at DD permanent

    d(A,D)=9d(A,D)=9

    The smallest temporary label can never be improved, so it becomes permanent.

  7. Make the label at EE permanent

    d(A,E)=11d(A,E)=11

    The smallest temporary label can never be improved, so it becomes permanent.

  8. Make the label at FF permanent

    d(A,F)=16d(A,F)=16

    The smallest temporary label can never be improved, so it becomes permanent.

  9. Add the weights along the shortest route

    A→B→C→D→E→F: 4+2+3+2+5=16A\to B\to C\to D\to E\to F:\ 4+2+3+2+5=16

    Tracing the route back from FF gives the least-weight path.

  10. Compare with the other routes

    A→B→C→D→E→F=16,A→C→D→E→F=17,A→B→C→E→F=17,A→B→C→D→F=17A\to B\to C\to D\to E\to F=16,\quad A\to C\to D\to E\to F=17,\quad A\to B\to C\to E\to F=17,\quad A\to B\to C\to D\to F=17

    Every other route from AA to FF is heavier.

  11. Work out the degree of every vertex

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

    For each vertex, count how many edges have that vertex as an endpoint.

  12. Recall the handshaking lemma

    ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v\in V}\deg(v)=2|E|

    The degrees of all the vertices add up to twice the number of edges.

  13. Recall that the number of odd vertices is even

    #{v:deg⁡(v) odd}≡0(mod2)\#\{v:\deg(v)\text{ odd}\}\equiv 0\pmod 2

    This follows at once from the handshaking lemma.

  14. Recall the condition for an Eulerian graph

    Eulerian  ⟺  connected and every vertex has even degree\text{Eulerian}\iff\text{connected and every vertex has even degree}

    An Eulerian circuit uses every edge exactly once and returns to its start.

  15. Select the shortest route

    A→B→C→D→E→F (weight 16)A\to B\to C\to D\to E\to F\ (\text{weight }16)

    This route has the least total weight.

Answer
A→B→C→D→E→F (weight 16)A\to B\to C\to D\to E\to F\ (\text{weight }16)
Question 3
9 markschallenging
The graph GG has vertex set V={A,B,C,D,E,F,G}V=\{A,B,C,D,E,F,G\} and edge set E={AB,AC,BD,BE,CF,CG,EF}E=\{AB,AC,BD,BE,CF,CG,EF\}. Determine whether GG is a tree. Which statement is correct?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E,F,G},E={AB,AC,BD,BE,CF,CG,EF}V=\{A,B,C,D,E,F,G\},\quad E=\{AB,AC,BD,BE,CF,CG,EF\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

    ∣V∣=7,∣E∣=7|V|=7,\quad |E|=7

    The graph has 7 vertices and 7 edges.

  3. Trace a search through the graph from AA

    {A,B,C,D,E,F,G} reached\{A,B,C,D,E,F,G\}\ \text{reached}

    A breadth-first search from AA reaches 7 of the 7 vertices.

  4. Test whether GG is connected

    c=1c=1

    A tree must be connected.

  5. Compare the number of edges with the number of vertices

    ∣E∣−∣V∣+c=7−7+1=1|E|-|V|+c=7-7+1=1

    A graph is a forest exactly when this cycle rank is 00.

  6. Look for a cycle in GG

    cycle present=yes\text{cycle present}=\text{yes}

    A tree contains no cycle at all.

  7. Compare ∣E∣|E| with ∣V∣−1|V|-1

    ∣E∣=7,∣V∣−1=6|E|=7,\quad |V|-1=6

    A tree on nn vertices has exactly n−1n-1 edges.

  8. Work out the degree of every vertex

    deg⁡(A)=2,deg⁡(B)=3,deg⁡(C)=3,deg⁡(D)=1,deg⁡(E)=2,deg⁡(F)=2,deg⁡(G)=1\deg(A)=2,\quad \deg(B)=3,\quad \deg(C)=3,\quad \deg(D)=1,\quad \deg(E)=2,\quad \deg(F)=2,\quad \deg(G)=1

    For each vertex, count how many edges have that vertex as an endpoint.

  9. Find the degree of vertex AA

    A: AB,AC ⇒ deg⁡(A)=2A:\ AB,AC\ \Rightarrow\ \deg(A)=2

    AA is joined to BB, CC. The degree (valency) of a vertex is the number of edges at it.

  10. Find the degree of vertex BB

    B: BA,BD,BE ⇒ deg⁡(B)=3B:\ BA,BD,BE\ \Rightarrow\ \deg(B)=3

    BB is joined to AA, DD, EE. The degree (valency) of a vertex is the number of edges at it.

  11. Find the degree of vertex CC

    C: CA,CF,CG ⇒ deg⁡(C)=3C:\ CA,CF,CG\ \Rightarrow\ \deg(C)=3

    CC is joined to AA, FF, GG. The degree (valency) of a vertex is the number of edges at it.

  12. Find the degree of vertex DD

    D: DB ⇒ deg⁡(D)=1D:\ DB\ \Rightarrow\ \deg(D)=1

    DD is joined to BB. The degree (valency) of a vertex is the number of edges at it.

  13. Find the degree of vertex EE

    E: EB,EF ⇒ deg⁡(E)=2E:\ EB,EF\ \Rightarrow\ \deg(E)=2

    EE is joined to BB, FF. The degree (valency) of a vertex is the number of edges at it.

  14. Find the degree of vertex FF

    F: FC,FE ⇒ deg⁡(F)=2F:\ FC,FE\ \Rightarrow\ \deg(F)=2

    FF is joined to CC, EE. The degree (valency) of a vertex is the number of edges at it.

  15. Find the degree of vertex GG

    G: GC ⇒ deg⁡(G)=1G:\ GC\ \Rightarrow\ \deg(G)=1

    GG is joined to CC. The degree (valency) of a vertex is the number of edges at it.

  16. Add the degrees of all the vertices

    ∑v∈Vdeg⁡(v)=2+3+3+1+2+2+1=14\sum_{v\in V}\deg(v)=2+3+3+1+2+2+1=14

    The degree sum counts each edge twice, once at each end.

  17. Select the correct statement

    G is not a treeG\ \text{is not a tree}

    A tree is a connected graph with no cycles.

Answer
G is not a treeG\ \text{is not a tree}
Question 4
9 markschallenging
The graph GG has vertex set V={A,B,C,D,E,F}V=\{A,B,C,D,E,F\} and edge set E={AB,BC,AD,BE,CF,DE,EF}E=\{AB,BC,AD,BE,CF,DE,EF\}. Determine whether GG is bipartite. Which statement is correct?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E,F},E={AB,BC,AD,BE,CF,DE,EF}V=\{A,B,C,D,E,F\},\quad E=\{AB,BC,AD,BE,CF,DE,EF\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

    ∣V∣=6,∣E∣=7|V|=6,\quad |E|=7

    The graph has 6 vertices and 7 edges.

  3. Colour the vertices with two colours

    {A,C,E} and {B,D,F}\{A,C,E\}\ \text{and}\ \{B,D,F\}

    No edge joins two vertices of the same colour, so the graph is bipartite.

  4. Work out the degree of every vertex

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

    For each vertex, count how many edges have that vertex as an endpoint.

  5. Try to two-colour the vertices, starting at AA

    colour(A)=1\text{colour}(A)=1

    Neighbours of a vertex must always take the other colour.

  6. State the test for bipartiteness

    bipartite  ⟺  no cycle of odd length\text{bipartite}\iff\text{no cycle of odd length}

    Odd cycles are exactly what stops a two-colouring from working.

  7. Trace a search through the graph from AA

    {A,B,D,C,E,F} reached\{A,B,D,C,E,F\}\ \text{reached}

    A breadth-first search from AA reaches 6 of the 6 vertices.

  8. Find the degree of vertex AA

    A: AB,AD ⇒ deg⁡(A)=2A:\ AB,AD\ \Rightarrow\ \deg(A)=2

    AA is joined to BB, DD. The degree (valency) of a vertex is the number of edges at it.

  9. Find the degree of vertex BB

    B: BA,BC,BE ⇒ deg⁡(B)=3B:\ BA,BC,BE\ \Rightarrow\ \deg(B)=3

    BB is joined to AA, CC, EE. The degree (valency) of a vertex is the number of edges at it.

  10. Find the degree of vertex CC

    C: CB,CF ⇒ deg⁡(C)=2C:\ CB,CF\ \Rightarrow\ \deg(C)=2

    CC is joined to BB, FF. The degree (valency) of a vertex is the number of edges at it.

  11. Find the degree of vertex DD

    D: DA,DE ⇒ deg⁡(D)=2D:\ DA,DE\ \Rightarrow\ \deg(D)=2

    DD is joined to AA, EE. The degree (valency) of a vertex is the number of edges at it.

  12. Find the degree of vertex EE

    E: EB,ED,EF ⇒ deg⁡(E)=3E:\ EB,ED,EF\ \Rightarrow\ \deg(E)=3

    EE is joined to BB, DD, FF. The degree (valency) of a vertex is the number of edges at it.

  13. Find the degree of vertex FF

    F: FC,FE ⇒ deg⁡(F)=2F:\ FC,FE\ \Rightarrow\ \deg(F)=2

    FF is joined to CC, EE. The degree (valency) of a vertex is the number of edges at it.

  14. Add the degrees of all the vertices

    ∑v∈Vdeg⁡(v)=2+3+2+2+3+2=14\sum_{v\in V}\deg(v)=2+3+2+2+3+2=14

    The degree sum counts each edge twice, once at each end.

  15. Apply the handshaking lemma

    ∑v∈Vdeg⁡(v)=2∣E∣=2×7=14\sum_{v\in V}\deg(v)=2|E|=2\times 7=14

    Every edge contributes 11 to the degree of each of its two endpoints.

  16. Select the correct statement

    G is bipartiteG\ \text{is bipartite}

    The two-colouring settles the question.

Answer
G is bipartiteG\ \text{is bipartite}
Question 5
9 markschallenging
The graph GG has vertex set V={A,B,C,D,E,F}V=\{A,B,C,D,E,F\} and edge set E={AB,BC,CA,DE,EF,FD,AD,BE,CF}E=\{AB,BC,CA,DE,EF,FD,AD,BE,CF\}. Determine whether GG has a Hamiltonian cycle. Which statement is correct?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E,F},E={AB,BC,CA,DE,EF,FD,AD,BE,CF}V=\{A,B,C,D,E,F\},\quad E=\{AB,BC,CA,DE,EF,FD,AD,BE,CF\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

    ∣V∣=6,∣E∣=9|V|=6,\quad |E|=9

    The graph has 6 vertices and 9 edges.

  3. Work out the degree of every vertex

    deg⁡(A)=3,deg⁡(B)=3,deg⁡(C)=3,deg⁡(D)=3,deg⁡(E)=3,deg⁡(F)=3\deg(A)=3,\quad \deg(B)=3,\quad \deg(C)=3,\quad \deg(D)=3,\quad \deg(E)=3,\quad \deg(F)=3

    For each vertex, count how many edges have that vertex as an endpoint.

  4. State what a Hamiltonian cycle is

    closed walk visiting each of the 6 vertices exactly once\text{closed walk visiting each of the }6\text{ vertices exactly once}

    It need not use every edge.

  5. Fix the starting vertex

    start at A\text{start at }A

    Any Hamiltonian cycle can be rotated so that it begins at AA.

  6. Count the orderings to be tested

    (6−1)!=120\left(6-1\right)!=120

    Each ordering of the remaining vertices gives one candidate cycle.

  7. Count the orderings that really are cycles

    valid orderings=6\text{valid orderings}=6

    An ordering works only if every consecutive pair, and the closing pair, is an edge.

  8. Search for a cycle through every vertex

    A→B→C→F→E→D→AA\to B\to C\to F\to E\to D\to A

    This closed walk visits each of the 6 vertices exactly once, so it is a Hamiltonian cycle.

  9. Trace a search through the graph from AA

    {A,B,C,D,E,F} reached\{A,B,C,D,E,F\}\ \text{reached}

    A breadth-first search from AA reaches 6 of the 6 vertices.

  10. Find the degree of vertex AA

    A: AB,AC,AD ⇒ deg⁡(A)=3A:\ AB,AC,AD\ \Rightarrow\ \deg(A)=3

    AA is joined to BB, CC, DD. The degree (valency) of a vertex is the number of edges at it.

  11. Find the degree of vertex BB

    B: BA,BC,BE ⇒ deg⁡(B)=3B:\ BA,BC,BE\ \Rightarrow\ \deg(B)=3

    BB is joined to AA, CC, EE. The degree (valency) of a vertex is the number of edges at it.

  12. Find the degree of vertex CC

    C: CA,CB,CF ⇒ deg⁡(C)=3C:\ CA,CB,CF\ \Rightarrow\ \deg(C)=3

    CC is joined to AA, BB, FF. The degree (valency) of a vertex is the number of edges at it.

  13. Find the degree of vertex DD

    D: DA,DE,DF ⇒ deg⁡(D)=3D:\ DA,DE,DF\ \Rightarrow\ \deg(D)=3

    DD is joined to AA, EE, FF. The degree (valency) of a vertex is the number of edges at it.

  14. Find the degree of vertex EE

    E: EB,ED,EF ⇒ deg⁡(E)=3E:\ EB,ED,EF\ \Rightarrow\ \deg(E)=3

    EE is joined to BB, DD, FF. The degree (valency) of a vertex is the number of edges at it.

  15. Select the correct statement

    G has a Hamiltonian cycleG\ \text{has a Hamiltonian cycle}

    The exhaustive search settles the question.

Answer
G has a Hamiltonian cycleG\ \text{has a Hamiltonian cycle}

Unlock 29 more Graphs and networks questions

Create a free account to work through every Further Maths Graphs and networks 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 Graphs and networks practice

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks