Graphs and networks Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Graphs and networks questions. See exactly how to solve problems on degree, valency, terminology, handshaking-lemma.

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.

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}V=\{A,B,C,D\} and edge set E={AB,AC,AD,BC,BD,CD}E=\{AB,AC,AD,BC,BD,CD\}. Write down the degree of vertex AA.

Worked solution

  1. Write down the vertex set and the edge set

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

    The graph is completely described by these two lists.

  2. Pick out the edges that involve AA

    AB,AC,AD

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

  3. State the degree of AA

    deg⁡(A)=3\deg(A)=3

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

Answer
deg⁡(A)=3\deg(A)=3
Question 3
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}E=\{AB,AC,AD,AE\}. Write down the degree of vertex AA.

Worked solution

  1. Write down the vertex set and the edge set

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

    The graph is completely described by these two lists.

  2. Pick out the edges that involve AA

    AB,AC,AD,AE

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

  3. Count the vertices and the edges

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

    The graph has 5 vertices and 4 edges.

  4. State the degree of AA

    deg⁡(A)=4\deg(A)=4

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

Answer
deg⁡(A)=4\deg(A)=4
Question 4
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,BC,CD,DE,EA}E=\{AB,BC,CD,DE,EA\}. Write down the degree of vertex CC.

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. Pick out the edges that involve CC

    CB,CD

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

  3. State the degree of CC

    deg⁡(C)=2\deg(C)=2

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

Answer
deg⁡(C)=2\deg(C)=2
Question 5
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,DA}E=\{AB,BC,CD,DA\}. Find the sum of the degrees of all the vertices of GG.

Worked solution

  1. Write down the vertex set and the edge set

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

    The graph is completely described by these two lists.

  2. Count the vertices and the edges

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

    The graph has 4 vertices and 4 edges.

  3. State the sum of the degrees

    ∑v∈Vdeg⁡(v)=8\sum_{v\in V}\deg(v)=8

    By the handshaking lemma this is twice the number of edges.

Answer
∑v∈Vdeg⁡(v)=8\sum_{v\in V}\deg(v)=8

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 QuestionsPractice Questions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks