Isomorphism of graphsAQA A-Level Further Maths: Mind map

Exam questions on Isomorphism of graphs

1. Graph $G$ has 6 vertices, 8 edges and degree sequence 4, 3, 3, 2, 2, 2.
   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
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.
   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
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$.
   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