Proving Isomorphism With Explicit Bijections

From a Candidate Map to a Proof

Graph invariants can rule out an isomorphism or help identify plausible vertex correspondences, but matching invariants alone does not prove that two graphs are isomorphic. A proof needs an explicit correspondence between their vertices and a verification that it preserves adjacency. The most reliable method is to write down the vertex map, check that it is a bijection, and compute the image of the entire edge set.

Throughout, graphs are finite and simple: they have no loops or multiple edges, and their edges are unordered pairs of distinct vertices. Thus \(uv\) and \(vu\) denote the same edge. For a graph \(G=(V,E)\), its vertex set and edge set are also written \(V(G)\) and \(E(G)\).

For an edge set \(E\), the image under \(\varphi\) is the set $$ \varphi(E)=\{\varphi(u)\varphi(v):uv\in E\}. $$ A useful verification method is to show that \(\varphi\) is a bijection and \(\varphi(E)=F\). Indeed, the equality says that every edge of \(G\) maps to an edge of \(H\), and that every edge of \(H\) comes from an edge of \(G\). Because \(\varphi\) is a bijection, each pair of target vertices has a unique pair of preimages; the edge-set equality therefore also rules out a target edge whose preimage pair is not an edge.

Checking Explicit Bijections

In a small example, keep the two checks separate. First verify that every vertex of the source has exactly one image and that these images are all the target vertices. Then compute the image of each source edge, remembering that the order of the endpoints does not matter. Finally compare the resulting set with the target edge set. If the sets agree, the map is an isomorphism.

In an undirected graph, writing an edge in the reverse order does not create a new edge: \(uv=vu\). This convention matters when comparing computed image sets with a proposed target. Treating reversed notation as a different edge can hide a missing edge or suggest that a list has the wrong number of distinct edges.

Isomorphism Is an Equivalence Relation

The explicit-map definition also gives three basic structural properties. A relation is an equivalence relation if it is reflexive, symmetric, and transitive. The proof here uses the identity map, inverse maps, and compositions of bijections; each construction must also preserve the required edge relation.

Proof. Let \(G=(V,E)\). For reflexivity, use the identity map \(\operatorname{id}_V:V\to V\), defined by \(\operatorname{id}_V(v)=v\) for every \(v\in V\). It is a bijection, and for every pair of distinct vertices \(u,v\), \(uv\in E\) if and only if \(\operatorname{id}_V(u)\operatorname{id}_V(v)=uv\in E\). Thus \(G\) is isomorphic to itself. This also holds when \(V\) is empty: the empty map from the empty set to itself is a bijection, and there are no vertex pairs to check.

For symmetry, suppose \(\varphi:V(G)\to V(H)\) is an isomorphism. Its inverse \(\varphi^{-1}:V(H)\to V(G)\) is a bijection. For any distinct \(x,y\in V(H)\), set \(u=\varphi^{-1}(x)\) and \(v=\varphi^{-1}(y)\). Since \(\varphi\) is an isomorphism, \(uv\in E(G)\) if and only if \(\varphi(u)\varphi(v)=xy\in E(H)\). Reversing the sides gives \(xy\in E(H)\) if and only if \(\varphi^{-1}(x)\varphi^{-1}(y)\in E(G)\), so \(\varphi^{-1}\) is an isomorphism from \(H\) to \(G\).

For transitivity, suppose \(\varphi:V(G)\to V(H)\) and \(\psi:V(H)\to V(K)\) are isomorphisms. Their composition \(\psi\circ\varphi:V(G)\to V(K)\) is a bijection, because each map is a bijection. For any distinct \(u,v\in V(G)\), the two isomorphism conditions give $$ uv\in E(G) \quad\Longleftrightarrow\quad \varphi(u)\varphi(v)\in E(H) \quad\Longleftrightarrow\quad \psi(\varphi(u))\psi(\varphi(v))\in E(K). $$ The last condition says exactly that the images of \(u,v\) under \(\psi\circ\varphi\) are adjacent in \(K\). Hence \(\psi\circ\varphi\) is an isomorphism from \(G\) to \(K\). If any vertex set is empty, the existence of the stated bijections forces the other sets in that comparison to be empty as well; the empty composition is a bijection and the adjacency condition has no pairs to check. Thus the three properties hold in all cases. \(\square\)

These properties let us treat graphs as equivalent up to relabeling. Reflexivity gives a graph in its own equivalence class, symmetry means that the direction of an isomorphism does not matter, and transitivity means that a chain of verified correspondences can be composed. In practice, if a complicated graph is easier to compare with an intermediate graph, two explicit isomorphisms can be composed to obtain one direct isomorphism.

Common Pitfalls

Showing only that edges map to edges. If the definition is stated as “adjacency is preserved,” check that the intended meaning includes both directions. A bijection that sends every source edge to a target edge might still fail to account for all target edges. Comparing the full image set \(\varphi(E)\) with \(F\) checks both directions.

Checking the vertex map but not its bijectivity. A list of assignments is not automatically a bijection. Check that no two source vertices receive the same image and that every target vertex occurs. Without this, the map cannot establish graph isomorphism.

Reversing an undirected edge in a comparison. The notation \(51\) denotes the same edge as \(15\), not a new edge. In the second example, counting \(51\) separately would conceal a repeated edge and make a false edge-set comparison. Always compare sets of unordered pairs.

Using invariants as a substitute for a map. Matching degree lists or other invariants can help screen candidate pairs, but equality of an invariant does not itself provide an adjacency-preserving bijection. A complete proof still requires a specific map and a check of its edge images.