Identify isomorphic graphs practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Graphs and networks, Graphs and networks)

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 correspondence preserves which pairs of vertices are joined; the drawing layout is irrelevant \(\displaystyle A\leftrightarrow P,\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 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Graph types, subgraphs, connection models and method selection Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula Represent a network in a matrix Identify the network a connection matrix describes Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection Dijkstra's algorithm for shortest distances and routes Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms A full network investigation