Isomorphism of graphsAQA A-Level Further Maths: Flashcards

What these 12 flashcards ask

What does it mean for two graphs to be isomorphic?
Name three necessary conditions for isomorphism.
Are the necessary conditions sufficient?
What is a degree sequence?
Why must isomorphic graphs have the same degree sequence?
How do you prove two graphs are isomorphic?
How do you prove two graphs are not isomorphic?
Must isomorphic graphs have the same vertex labels?
Can isomorphic graphs be drawn differently?
Does a triangle in one graph and none in the other prove non-isomorphism?
How can you use adjacency matrices to check isomorphism?
A vertex of degree 3 in G maps to a vertex of what degree in H?

Exam questions on Isomorphism of graphs

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
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
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

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).