Isomorphism of graphsAQA A-Level Further Maths: Subtopic test

1. 1
   Graph $G$ has 6 vertices, 8 edges and degree sequence 4, 3, 3, 2, 2, 2.

   (a)

   Graph $H$ has 6 vertices and 7 edges. Can $G$ and $H$ be isomorphic?

   [1 mark]

   • ANo, because isomorphic graphs have the same number of edges
   • BYes, because both graphs have 6 vertices
   • CYes, because $H$ can be obtained from $G$ by deleting an edge
   • DOnly if the degree sequence of $H$ is 4, 3, 3, 2, 2, 2

   (b)

   Graph $H'$ has 6 vertices, 8 edges and degree sequence 4, 3, 3, 2, 2, 2. Which statement is correct?

   [1 mark]

   • A$H'$ is isomorphic to $G$, because the numbers of vertices and edges and the degree sequences agree
   • B$H'$ is not isomorphic to $G$, because the two graphs are not drawn identically
   • C$H'$ may or may not be isomorphic to $G$: these conditions are necessary but not sufficient
   • D$H'$ is isomorphic to $G$ only if the vertices are labelled in the same way

   (c)

   A graph $L$ has 6 vertices, 8 edges and degree sequence 4, 4, 2, 2, 2, 2. Explain why $L$ is not isomorphic to $G$.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Graph $P$ has vertices $A,B,C,D,E$ and edges $AB$, $BC$, $CD$, $DE$, $EA$ and $AC$. Graph $Q$ has vertices 1 to 5 and edges 12, 23, 34, 45, 51 and 25.

   (a)

   What is the degree sequence of $P$?

   [1 mark]

   • A$4, 2, 2, 2, 2$
   • B$3, 3, 2, 2, 2$
   • C$3, 2, 2, 2, 1$
   • D$3, 3, 3, 2, 1$

   (b)

   Which of the following is an isomorphism from $P$ to $Q$?

   [1 mark]

   • A$A\to1,\ B\to2,\ C\to3,\ D\to4,\ E\to5$
   • B$A\to2,\ B\to3,\ C\to5,\ D\to4,\ E\to1$
   • C$A\to3,\ B\to2,\ C\to1,\ D\to5,\ E\to4$
   • D$A\to2,\ B\to1,\ C\to5,\ D\to4,\ E\to3$

   (c)

   The graph $R$ has vertices 1 to 5 and edges 12, 23, 31, 34, 45 and 35. Explain why $R$ is not isomorphic to $P$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Graph $M$ has vertices $P,Q,R,S$ and adjacency matrix, with rows and columns in this order, $\begin{pmatrix} 0&1&1&0 \\ 1&0&1&1 \\ 1&1&0&0 \\ 0&1&0&0 \end{pmatrix}$. Graph $N$ has vertices $W,X,Y,Z$ and edges $WX$, $XY$, $YZ$ and $XZ$.

   (a)

   Show that $M$ and $N$ 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 $M$ and $N$ are isomorphic.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Graph $G_1$ is the complete bipartite graph $K_{3,3}$. Graph $G_2$ has vertices $U_1,U_2,U_3,V_1,V_2,V_3$ and nine edges: $U_1U_2$, $U_2U_3$, $U_3U_1$, $V_1V_2$, $V_2V_3$, $V_3V_1$, $U_1V_1$, $U_2V_2$ and $U_3V_3$.

   (a)

   Both graphs have 6 vertices, 9 edges and every vertex of degree 3. Show that nevertheless $G_1$ and $G_2$ are not isomorphic.

   [6 marks]

   (b)

   Graph $G_3$ has vertices 1 to 6 and edges 12, 23, 34, 45, 56, 61, 13, 25 and 46. Find an isomorphism from $G_2$ to $G_3$ and verify that it is one.

   [6 marks]

   Total for question 4: 12 marks

End of questions