Isomorphism of graphs

Isomorphism of graphs Test

Spec DA7 · 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

Isomorphism of graphs

Total 27 marks

Name

Class

Date

  1. 1
    Graph GG has 6 vertices, 8 edges and degree sequence 4, 3, 3, 2, 2, 2.
    (a)
    Graph HH has 6 vertices and 7 edges. Can GG and HH be isomorphic?
    [1 mark]
    • ANo, because isomorphic graphs have the same number of edges
    • BYes, because both graphs have 6 vertices
    • CYes, because HH can be obtained from GG by deleting an edge
    • DOnly if the degree sequence of HH is 4, 3, 3, 2, 2, 2
    (b)
    Graph H′H' has 6 vertices, 8 edges and degree sequence 4, 3, 3, 2, 2, 2. Which statement is correct?
    [1 mark]
    • AH′H' is isomorphic to GG, because the numbers of vertices and edges and the degree sequences agree
    • BH′H' is not isomorphic to GG, because the two graphs are not drawn identically
    • CH′H' may or may not be isomorphic to GG: these conditions are necessary but not sufficient
    • DH′H' is isomorphic to GG only if the vertices are labelled in the same way
    (c)
    A graph LL has 6 vertices, 8 edges and degree sequence 4, 4, 2, 2, 2, 2. Explain why LL is not isomorphic to GG.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    Graph PP has vertices A,B,C,D,EA,B,C,D,E and edges ABAB, BCBC, CDCD, DEDE, EAEA and ACAC. Graph QQ has vertices 1 to 5 and edges 12, 23, 34, 45, 51 and 25.
    (a)
    What is the degree sequence of PP?
    [1 mark]
    • A4,2,2,2,24, 2, 2, 2, 2
    • B3,3,2,2,23, 3, 2, 2, 2
    • C3,2,2,2,13, 2, 2, 2, 1
    • D3,3,3,2,13, 3, 3, 2, 1
    (b)
    Which of the following is an isomorphism from PP to QQ?
    [1 mark]
    • AA→1, B→2, C→3, D→4, E→5A\to1,\ B\to2,\ C\to3,\ D\to4,\ E\to5
    • BA→2, B→3, C→5, D→4, E→1A\to2,\ B\to3,\ C\to5,\ D\to4,\ E\to1
    • CA→3, B→2, C→1, D→5, E→4A\to3,\ B\to2,\ C\to1,\ D\to5,\ E\to4
    • DA→2, B→1, C→5, D→4, E→3A\to2,\ B\to1,\ C\to5,\ D\to4,\ E\to3
    (c)
    The graph RR has vertices 1 to 5 and edges 12, 23, 31, 34, 45 and 35. Explain why RR is not isomorphic to PP.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    Graph MM has vertices P,Q,R,SP,Q,R,S and adjacency matrix, with rows and columns in this order, (0110101111000100)\begin{pmatrix} 0&1&1&0 \\ 1&0&1&1 \\ 1&1&0&0 \\ 0&1&0&0 \end{pmatrix}. Graph NN has vertices W,X,Y,ZW,X,Y,Z and edges WXWX, XYXY, YZYZ and XZXZ.
    (a)
    Show that MM and NN satisfy the necessary conditions for isomorphism: the same number of vertices, the same number of edges and the same degree sequence.
    [3 marks]
    (b)
    Prove that MM and NN are isomorphic.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    Graph G1G_1 is the complete bipartite graph K3,3K_{3,3}. Graph G2G_2 has vertices U1,U2,U3,V1,V2,V3U_1,U_2,U_3,V_1,V_2,V_3 and nine edges: U1U2U_1U_2, U2U3U_2U_3, U3U1U_3U_1, V1V2V_1V_2, V2V3V_2V_3, V3V1V_3V_1, U1V1U_1V_1, U2V2U_2V_2 and U3V3U_3V_3.
    (a)
    Both graphs have 6 vertices, 9 edges and every vertex of degree 3. Show that nevertheless G1G_1 and G2G_2 are not isomorphic.
    [6 marks]
    (b)
    Graph G3G_3 has vertices 1 to 6 and edges 12, 23, 34, 45, 56, 61, 13, 25 and 46. Find an isomorphism from G2G_2 to G3G_3 and verify that it is one.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests