Graph theory terminology

Graph theory terminology Test

Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

Graph theory terminology

Total 27 marks

Name

Class

Date

  1. 1
    A graph GG has vertices A,B,C,D,EA, B, C, D, E and edges ABAB, ACAC, BCBC, CDCD and DEDE.
    (a)
    What is the degree of vertex CC?
    [1 mark]
    • A22
    • B33
    • C44
    • D55
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Which of the following is a cycle in GG?
    [1 mark]
    • AA→B→C→AA\to B\to C\to A
    • BC→D→EC\to D\to E
    • CA→B→C→D→EA\to B\to C\to D\to E
    • DA→C→D→C→AA\to C\to D\to C\to A
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    State, with a reason, whether GG is a tree.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: it is not a tree
    B1: it contains a cycle (
    ABCAABCA), or it has 5 edges but a tree on 5 vertices has only 4

    Total for question 1: 4 marks

  2. 2
    KK is the complete graph with 6 vertices.
    (a)
    How many edges does KK have?
    [1 mark]
    • A1212
    • B3030
    • C1515
    • D3636
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    What is the degree of each vertex of KK?
    [1 mark]
    • A66
    • B1515
    • C44
    • D55
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    A spanning tree of KK is formed by deleting edges. State the number of edges in the spanning tree and the number of edges deleted.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: 55 edges in the spanning tree (6 vertices, so 6−16-1)
    B1:
    15−5=1015-5=10 edges deleted
    Accept: follow-through from their number of edges in
    KK

    Total for question 2: 4 marks

  3. 3
    A graph HH has vertices P,Q,R,S,T,UP, Q, R, S, T, U and edges PQPQ, QRQR, RSRS, STST, TUTU, UPUP and QTQT.
    (a)
    (i) Write down a cycle in HH that contains exactly four vertices.
    (ii) Write down a walk in
    HH of five edges that is not a path.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) QRSTQQRSTQ or PQTUPPQTUP
    M1: (ii) a walk of five edges, each an edge of
    HH, with consecutive edges sharing a vertex
    A1: (ii) a vertex repeated, so it is not a path, e.g.
    PQRQTUPQRQTU
    Accept: any valid walk that repeats a vertex or edge
    (b)
    (i) State the number of edges in a spanning tree of HH, and hence the number of edges that must be removed from HH to form one.
    (ii) List the edges of one spanning tree of
    HH.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) 55 edges in a spanning tree
    B1: (i)
    7−5=27-5=2 edges removed
    M1: (ii) five edges of
    HH that include all six vertices
    A1: (ii) connected with no cycle, e.g.
    PQ,QR,ST,TU,QTPQ, QR, ST, TU, QT
    Accept: any valid spanning tree of
    HH

    Total for question 3: 7 marks

  4. 4
    A network of 8 computers is modelled by a connected graph GG. Each vertex represents a computer and each edge represents a cable. No computer is joined to itself and each pair of computers is joined by at most one cable.
    (a)
    The network has 10 cables.
    (i) Find the sum of the degrees of the vertices and the mean degree.

    (ii) Explain why
    GG cannot have exactly three vertices of odd degree.
    (iii) Show that
    GG contains a cycle, and find the number of cables that must be removed to leave a spanning tree.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) sum of degrees 2020
    B1: (i) mean degree
    2.52.5
    B1: (ii) the sum of the degrees is twice the number of edges, so it is even

    B1: (ii) with exactly three odd degrees the sum would be odd, which is impossible

    M1: (iii) a tree on 8 vertices has 7 edges, and
    GG has 10>710>7 edges
    A1: (iii) so
    GG contains a cycle, and 10−7=310-7=3 cables are removed
    (b)
    (i) Find the number of cables in the complete graph on the 8 computers, and the degree of each vertex.
    (ii) A technician claims that if every vertex of
    GG has degree 3 then GG is a tree. Show that the claim is false.
    (iii) Explain why a tree with 8 vertices must have at least one vertex of degree 1.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) 8×72=28\frac{8\times7}{2}=28 cables
    B1: (i) degree
    77
    M1: (ii) sum of degrees
    8×3=248\times3=24, so 1212 edges
    A1: (ii) a tree on 8 vertices has 7 edges, so
    GG is not a tree
    M1: (iii) a tree has 7 edges, so the degrees sum to
    1414
    A1: (iii) if every degree were at least 2 the sum would be at least
    16>1416>14, so some vertex has degree 1 (degree 0 is impossible as the tree is connected)

    Total for question 4: 12 marks

End of questions

Subtopic tests