Language and properties of graphs

Language and properties of graphs Test

Spec DA1–DA2 · AQA A-Level Further 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

AQA A-Level Further Maths

Language and properties of graphs

Total 27 marks

Name

Class

Date

  1. 1
    A graph GG has vertices A, B, C, D, EA,\ B,\ C,\ D,\ E and seven edges: ABAB, ACAC, BCBC, BDBD, CDCD, CECE and DEDE.
    (a)
    Write down the degree of vertex CC.
    [1 mark]
    • A44
    • B33
    • C22
    • D77
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Which statement about GG is correct?
    [1 mark]
    • AGG is Eulerian, because every vertex has even degree
    • BGG is Eulerian, because it is connected and contains a cycle
    • CGG is neither Eulerian nor semi-Eulerian, because it has a vertex of degree 44
    • DGG is semi-Eulerian, because exactly two vertices (BB and DD) have odd degree
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Write down a trail in GG that uses every edge exactly once.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: a trail that starts at BB and ends at DD (or starts at DD and ends at BB)
    A1: all seven edges used exactly once, e.g.
    B A C B D C E DB\,A\,C\,B\,D\,C\,E\,D
    Accept: any valid Eulerian trail, such as
    D E C D B C A BD\,E\,C\,D\,B\,C\,A\,B

    Total for question 1: 4 marks

  2. 2
    A graph HH has vertices P, Q, R, S, T, UP,\ Q,\ R,\ S,\ T,\ U and eight edges: PQPQ, QRQR, RSRS, STST, TUTU, UPUP, PSPS and QTQT.
    (a)
    How many vertices of HH have odd degree?
    [1 mark]
    • A22
    • B33
    • C44
    • D66
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Which of these is a Hamiltonian cycle of HH?
    [1 mark]
    • AP→Q→R→S→PP\to Q\to R\to S\to P
    • BP→Q→R→S→T→U→PP\to Q\to R\to S\to T\to U\to P
    • CP→Q→R→S→T→UP\to Q\to R\to S\to T\to U
    • DP→Q→T→U→PP\to Q\to T\to U\to P
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Explain why HH is neither Eulerian nor semi-Eulerian.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: PP, QQ, SS and TT have odd degree (degree 33), so there are four odd vertices
    A1: an Eulerian graph has no odd vertices and a semi-Eulerian graph has exactly two, so
    HH is neither

    Total for question 2: 4 marks

  3. 3
    A connected simple graph KK has six vertices. Five of the vertices have degrees 2, 2, 3, 32,\ 2,\ 3,\ 3 and 44, and the sixth vertex has degree xx.
    (a)
    Show that xx is even, and state with a reason whether KK is Eulerian, semi-Eulerian or neither.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: the sum of the degrees equals twice the number of edges, so it is even
    M1:
    2+2+3+3+4+x=14+x2+2+3+3+4+x=14+x is even, so xx is even
    A1: exactly two vertices (the two of degree
    33) have odd degree, so KK is semi-Eulerian (not Eulerian)
    (b)
    Given that x=4x=4:
    (i) find the number of edges of
    KK;
    (ii) a new graph
    K′K' is formed by subdividing one edge of KK with a new vertex. State the number of vertices and the number of edges of K′K'.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) 2+2+3+3+4+4=182+2+3+3+4+4=18, and the number of edges is half of this
    A1: (i)
    99 edges
    B1: (ii)
    77 vertices
    B1: (ii)
    1010 edges (one edge is replaced by two)

    Total for question 3: 7 marks

  4. 4
    A park has six junctions A, B, C, D, EA,\ B,\ C,\ D,\ E and FF joined by seven paths: ABAB, BCBC, CDCD, DEDE, EFEF, FAFA and ADAD.
    (a)
    (i) Show that there is a route that uses every path exactly once, and write one down.
    (ii) Explain why no such route can start and finish at the same junction, and suggest one extra path that would make this possible.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) degrees: AA and DD have degree 33 and BB, CC, EE, FF have degree 22
    A1: (i) the graph is connected with exactly two odd vertices, so it is semi-Eulerian and the route exists

    B1: (i) a valid trail starting at
    AA and ending at DD (or the reverse), e.g. A B C D E F A DA\,B\,C\,D\,E\,F\,A\,D
    R1: (ii) a closed route needs every vertex to have even degree, but
    AA and DD have odd degree
    M1: (ii) a second path joining
    AA and DD
    A1: (ii) the degrees of
    AA and DD become 44, so all degrees are even and the graph is Eulerian
    (b)
    (i) Show that the graph is Hamiltonian.
    (ii) The junction
    FF and its two paths are closed. For the network that remains, determine whether it is Eulerian, semi-Eulerian or neither, and whether it is Hamiltonian.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) a cycle through all six junctions, e.g. A B C D E F AA\,B\,C\,D\,E\,F\,A
    B1: (i) every junction appears once, and the cycle returns to
    AA using FAFA
    M1: (ii) degrees:
    A:2A:2, B:2B:2, C:2C:2, D:3D:3, E:1E:1
    A1: (ii) exactly two odd vertices (
    DD and EE) and connected, so semi-Eulerian
    R1: (ii)
    EE has degree 11, and a cycle needs two edges at every vertex it contains, so EE cannot be on a cycle
    A1: (ii) the network is not Hamiltonian

    Total for question 4: 12 marks

End of questions

Subtopic tests