Isomorphism of graphs Quiz

1. Which is NOT required for two graphs to be isomorphic?

• A. Same number of vertices
• B. Same number of edges
• C. Same vertex labels
• D. Same degree sequence

2. Two graphs each have 5 vertices, 6 edges and degree sequence 3, 3, 2, 2, 2. Can you conclude they are isomorphic?

• A. Yes
• B. No: these conditions are only necessary, so a further check is needed
• C. No: graphs with 5 vertices are never isomorphic
• D. Only if they are drawn the same way

3. Graph $G$ contains a triangle; graph $H$ does not. Both have 6 vertices and 8 edges. Are they isomorphic?

• A. No: an isomorphism preserves triangles
• B. Yes: the numbers of vertices and edges agree
• C. Yes: if their degree sequences agree
• D. It cannot be decided

4. An isomorphism sends a vertex of degree 3 to a vertex of degree

• A. 2
• B. 4
• C. 1
• D. 3

5. An isomorphism $f$ from $G$ to $H$ is applied to an edge $uv$ of $G$. Then

• A. $f(u)$ and $f(v)$ are not adjacent
• B. $u$ and $f(u)$ must have equal labels
• C. $f(u)f(v)$ is an edge of $H$
• D. $f(u)$ and $f(v)$ must be labelled consecutively