Special graphs

Special graphs Test

Spec DA5–DA6 · 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

Special graphs

Total 27 marks

Name

Class

Date

  1. 1
    A simple graph GG has 7 vertices and 8 edges.
    (a)
    How many edges does the complement of GG have?
    [1 mark]
    • A88
    • B2121
    • C1313
    • D1414
    (b)
    A vertex vv of GG has degree 2. What is the degree of vv in the complement of GG?
    [1 mark]
    • A22
    • B55
    • C66
    • D44
    (c)
    Explain why GG cannot be a tree.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    A graph has vertices PP, QQ, RR, SS, TT. Its adjacency matrix, with rows and columns in the order P,Q,R,S,TP,Q,R,S,T, is (0001100010000011100010100)\begin{pmatrix} 0&0&0&1&1 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \\ 1&1&0&0&0 \\ 1&0&1&0&0 \end{pmatrix}.
    (a)
    How many edges does the graph have?
    [1 mark]
    • A44
    • B88
    • C55
    • D1010
    (b)
    Which statement about the graph is correct?
    [1 mark]
    • AIt is a complete bipartite graph
    • BIt is a tree
    • CIt contains a cycle
    • DIt is a complete graph
    (c)
    Show that the graph is bipartite, stating the two sets of vertices.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    GG is a simple connected graph with 6 vertices. The degrees of its vertices are 4, 4, 3, 2, 2, 1.
    (a)
    Show that GG has 8 edges and explain why GG is not a tree.
    [3 marks]
    (b)
    Let G′G' be the complement of GG. Find the degrees of the vertices of G′G', show that G′G' has 7 edges, and state with a reason whether G′G' is a tree.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    The complete bipartite graph K3,3K_{3,3} has vertex sets {A,B,C}\{A,B,C\} and {X,Y,Z}\{X,Y,Z\}, with every vertex in one set joined to every vertex in the other set. The graph GG is formed from K3,3K_{3,3} by deleting the three edges AXAX, BYBY and CZCZ.
    (a)
    (i) Show that GG has 6 edges.
    (ii) Write down the adjacency matrix of
    GG, with the vertices in the order A,B,C,X,Y,ZA,B,C,X,Y,Z.
    (iii) Write down the degree of every vertex of
    GG.
    [6 marks]
    (b)
    Let G′G' be the complement of GG.
    (i) Find the number of edges of
    G′G'.
    (ii) Write down the degree of each vertex of
    G′G'.
    (iii) Prove that
    G′G' is not bipartite.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests