Identify isomorphic graphs practice questions | General Mathematics (Year 11, VCE Units 1 & 2, Graphs and networks, Connected graphs, bridges and isomorphism)

Identify isomorphic graphs

Isomorphic graphs contain the same connection information after vertices are relabelled. Use counts and degrees as checks, then verify the actual connections under one correspondence

G\cong H

Match the vertex count Isomorphic graphs have the same number of vertices \(\displaystyle |V(G)|=|V(H)|\)
Match the edge count Isomorphic graphs have the same number of edges, including loops or parallel edges when present \(\displaystyle |E(G)|=|E(H)|\)
Match corresponding degrees Vertices that correspond under an isomorphism have equal degrees \(\displaystyle (3,2,3,2)_G=(3,2,3,2)_H\)
Check every connection A valid one-to-one correspondence preserves the number of edges joining each corresponding pair of vertices, including loops and parallel edges; the drawing layout is irrelevant \(\displaystyle A\leftrightarrow P,\quad B\leftrightarrow Q,\quad AB\in E(G)\Longleftrightarrow PQ\in E(H)\)

Worked example

Graph G has edges AB, AC, AD, BC and CD. Graph H has edges PQ, PR, PS, QR and RS. Decide whether G and H are isomorphic

E(G)=\{AB,AC,AD,BC,CD\},\quad E(H)=\{PQ,PR,PS,QR,RS\}

\(\displaystyle |V(G)|=|V(H)|=4\)Both graphs have four vertices
\(\displaystyle |E(G)|=|E(H)|=5\)Both edge lists contain five edges
\(\displaystyle (\deg A,\deg B,\deg C,\deg D)=(3,2,3,2)=(\deg P,\deg Q,\deg R,\deg S)\)The degrees match under the proposed order of the vertices
\(\displaystyle A\mapsto P,\;B\mapsto Q,\;C\mapsto R,\;D\mapsto S,\quad G\cong H\)This correspondence maps AB, AC, AD, BC and CD to PQ, PR, PS, QR and RS

Common mistakes

Using counts only

✕\(\displaystyle |V(G)|=|V(H)|,\quad |E(G)|=|E(H)|\Rightarrow G\cong H\)✓\(\displaystyle |V(G)|=|V(H)|,\quad |E(G)|=|E(H)|\text{ and all corresponding connections match}\Rightarrow G\cong H\)

Equal vertex and edge counts are necessary but do not prove that the connections match

Rejecting a different layout

✕\(\displaystyle \text{different layout}\Rightarrow G\not\cong H\)✓\(\displaystyle \text{same connections under relabelling}\Rightarrow G\cong H\)

The positions and shapes in a drawing can change while the vertex connections stay the same

Stopping at the degree sequence

✕\(\displaystyle \text{same degree sequence}\Rightarrow G\cong H\)✓\(\displaystyle \text{same degree sequence}\text{ plus a matching adjacency check}\Rightarrow G\cong H\)

Graphs can have the same degree sequence but different connections

Difficulty levels

introDecide a simple isomorphism verdict after comparing the graph counts

standardSelect an isomorphic candidate after checking counts, degrees and connections

challengeDistinguish candidates with equal counts and degree sequences by their connections

examSelect the relabelled graph that preserves all corresponding connections

Questions about this topic

What does it mean for two graphs to be isomorphic?+

There is a one-to-one correspondence between their vertices that preserves every connection. The labels and drawing layout may be different

Why are matching vertex and edge counts not enough?+

They are necessary checks, but two graphs with the same counts can join their vertices in different ways

Why compare vertex degrees when testing isomorphism?+

A correspondence must map each vertex to a vertex with the same number of attached edge-ends. A degree mismatch rules out isomorphism before the connections are checked

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 11, VCE Units 1 & 2, General Mathematics, chapter 8: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula 8C Euler's formula: A full network investigation Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification 8E Eulerian trails and circuits: A full network investigation Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection 8G Weighted graphs and shortest paths: A full network investigation Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms 8H Trees and minimum spanning trees: A full network investigation