Further Maths Graphs and networks Practice Questions

Free Further Maths Graphs and networks practice questions with full step-by-step worked solutions. Covers degree, valency, terminology, handshaking-lemma. Practise exam-style problems and check your method.

degreevalencyterminologyhandshaking-lemmaadjacency-matrixparity
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
The graph GG has vertex set V={A,B,C,D}V=\{A,B,C,D\} and edge set E={AB,BC,CD}E=\{AB,BC,CD\}. Write down the degree of vertex BB.
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D},E={AB,BC,CD}V=\{A,B,C,D\},\quad E=\{AB,BC,CD\}

    The graph is completely described by these two lists.

  2. Pick out the edges that involve BB

    BA,BC

    Every edge with BB as an endpoint counts once towards its degree.

  3. State the degree of BB

    deg⁡(B)=2\deg(B)=2

    The degree (valency) of a vertex is the number of edges at it.

Answer
deg⁡(B)=2\deg(B)=2
Question 2
2 markseasy
The graph GG has vertex set V={A,B,C,D,E}V=\{A,B,C,D,E\} and edge set E={AB,AC,AD,AE,BC,CD,DE,EB}E=\{AB,AC,AD,AE,BC,CD,DE,EB\}. Which vertex of GG has the largest degree?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E},E={AB,AC,AD,AE,BC,CD,DE,EB}V=\{A,B,C,D,E\},\quad E=\{AB,AC,AD,AE,BC,CD,DE,EB\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

    ∣V∣=5,∣E∣=8|V|=5,\quad |E|=8

    The graph has 5 vertices and 8 edges.

  3. Work out the degree of every vertex

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

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

  4. Select the vertex of largest degree

    deg⁡(A)=4=Δ(G)\deg(A)=4=\Delta(G)

    No other vertex has degree as large as 44.

Answer
deg⁡(A)=4\deg(A)=4
Question 3
4 marksintermediate
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\}. In GG, the vertex sequence A→B→E→B→AA\to B\to E\to B\to A is best described as which of the following?
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. Check that each consecutive pair is an edge of GG

    AB \inE,BE \inE,EB \inE,BA \inEAB\ \text{\in E},\quad BE\ \text{\in E},\quad EB\ \text{\in E},\quad BA\ \text{\in E}

    If any pair fails this test the sequence is not even a walk.

  4. Check for a repeated edge

    edges used=4,distinct edges=2\text{edges used}=4,\quad \text{distinct edges}=2

    A trail uses no edge more than once.

  5. Check for a repeated vertex

    vertices listed=5,distinct vertices=3\text{vertices listed}=5,\quad \text{distinct vertices}=3

    A path uses no vertex more than once.

  6. Select the correct description

    walk\text{walk}

    The sequence is a walk in GG, but not a trail.

Answer
walk\text{walk}
Question 4
6 markshard
The graph GG has vertex set V={A,B,C,D,E}V=\{A,B,C,D,E\} and edge set E={AB,BC,CD,DE,EA}E=\{AB,BC,CD,DE,EA\}. Which of the following is the adjacency matrix of GG, with the rows and the columns taken in the order A,B,C,D,EA,B,C,D,E?
Show worked solution

Worked solution

  1. Write down the vertex set and the edge set

    V={A,B,C,D,E},E={AB,BC,CD,DE,EA}V=\{A,B,C,D,E\},\quad E=\{AB,BC,CD,DE,EA\}

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

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

    The graph has 5 vertices and 5 edges.

  3. Set up an empty 5×55\times 5 array

    rows and columns in the order A,B,C,D,E\text{rows and columns in the order }A,B,C,D,E

    Entry (i,j)(i,j) will record whether ii and jj are joined.

  4. Enter a 11 for each edge, in both positions

    Aij=Aji=1 for every edge ij\mathbf{A}_{ij}=\mathbf{A}_{ji}=1\ \text{for every edge }ij

    The graph is undirected, so the matrix is symmetric.

  5. Note that the diagonal is zero

    Aii=0\mathbf{A}_{ii}=0

    The graph is simple, so no vertex is joined to itself.

  6. Write down the adjacency matrix of GG

    A=(0100110100010100010110010)\mathbf{A}=\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}

    The rows and columns are in the order A,B,C,D,EA,B,C,D,E; entry (i,j)(i,j) is 11 when vertices ii and jj are joined.

  7. Work out the degree of every vertex

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

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

  8. Find the degree of vertex AA

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

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

  9. Find the degree of vertex BB

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

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

  10. Find the degree of vertex CC

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

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

  11. Select the correct matrix

    A=(0100110100010100010110010)\mathbf{A}=\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}

    Its row sums are the degrees of the vertices.

Answer
A=(0100110100010100010110010)\mathbf{A}=\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}
Question 5
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)

Unlock 65 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

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks