Graph Isomorphisms and Relabeling

When Are Two Graphs the Same?

A graph can be described with different vertex labels without changing which vertices are joined. For example, replacing numerical labels by letters may make the same connections easier to read, but it does not create a new structure. To express this precisely, we need a correspondence between the vertices that preserves adjacency in both directions. This correspondence is called a graph isomorphism.

Throughout, graphs are finite and simple: an edge joins two distinct vertices, and no pair of vertices has more than one edge. For a graph $G=(V,E)$, its vertex set is $V(G)=V$ and its edge set is $E(G)=E$. We write $uv$ for the unordered edge joining $u$ and $v$. Two distinct vertices are adjacent when their pair is an edge.

Definition: Let $G=(V,E)$ and $H=(W,F)$ be finite simple graphs. An isomorphism from $G$ to $H$ is a bijection $\phi:V\to W$ such that, for every pair of distinct vertices $u,v\in V$, $$ uv\in E \quad\Longleftrightarrow\quad \phi(u)\phi(v)\in F. $$ If such a bijection exists, $G$ and $H$ are isomorphic, written $G\cong H$.

The condition is an if-and-only-if: edges must map to edges, and nonedges between distinct vertices must map to nonedges. A bijection that sends every edge to an edge but fails to preserve nonedges is not enough. Nor is it enough to match some of the vertices: every vertex of each graph must be included exactly once.

Isomorphic graphs need not be equal as set-theoretic objects. Their vertex sets may use different labels, and their edge sets then use those labels too. The claim $G\cong H$ means that a bijection identifies their adjacency patterns, not that $V(G)=V(H)$ or $E(G)=E(H)$.

Relabeling Transports the Edges

Suppose we choose new labels for the vertices of $G$ using a bijection $\phi:V\to W$. To retain the same graph structure, we must carry every edge along with its endpoints. Thus an edge $uv$ becomes the edge $\phi(u)\phi(v)$. No other edges are added, and none are deleted.

Proposition: Given a graph $G=(V,E)$ and a bijection $\phi:V\to W$, define a graph $H=(W,F)$ by $$ F=\{\phi(u)\phi(v):uv\in E\}. $$ Then $\phi$ is an isomorphism from $G$ to $H$. Conversely, if $\phi$ is an isomorphism from $G$ to $H$, then $H$'s edge set is exactly $\{\phi(u)\phi(v):uv\in E(G)\}$.

Proof. First suppose $H$ is defined by the displayed edge set. For distinct $u,v\in V$, if $uv\in E$, then $\phi(u)\phi(v)\in F$ by the definition of $F$. Conversely, suppose $\phi(u)\phi(v)\in F$. By the definition of $F$, this edge has the form $\phi(x)\phi(y)$ for some $xy\in E$. Since $\phi$ is a bijection, its images of distinct vertices are distinct, and the unordered pair $\{\phi(u),\phi(v)\}$ can equal $\{\phi(x),\phi(y)\}$ only when $\{u,v\}=\{x,y\}$. Hence $uv\in E$. So adjacency is preserved in both directions, and $\phi$ is an isomorphism. Conversely, if $\phi$ is an isomorphism, then each edge $uv\in E(G)$ maps to an edge $\phi(u)\phi(v)\in E(H)$. If $ab\in E(H)$, bijectivity gives unique vertices $u,v\in V(G)$ with $a=\phi(u)$ and $b=\phi(v)$; the isomorphism condition implies $uv\in E(G)$. Therefore the edge set of $H$ consists exactly of the transported edges. $\square$

This proposition makes the distinction precise: changing labels means changing the vertex names and transporting all the edges consistently. If the labels stay fixed but the edge set changes, that is a change to the graph as given. The resulting graph might still be isomorphic to the original by a different bijection, but that requires a separate correspondence.

Worked Example: Relabeling a Path

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. Let $H=(W,F)$ have $W=\{a,b,c,d\}$ and $F=\{ac,cd,bd\}$. Test the proposed bijection $\phi(1)=a,\ \phi(2)=c,\ \phi(3)=d,\ \phi(4)=b$.

The images of the three edges of $G$ are $12\mapsto ac$, $23\mapsto cd$, and $34\mapsto db=bd$. Each is in $F$. To check the reverse direction as well, list the three edges of $H$: $ac$ comes from $12$, $cd$ comes from $23$, and $bd$ comes from $34$. Thus the edge sets correspond exactly under $\phi$.

There are six unordered pairs of distinct vertices in $G$. Its nonedges are $13,14,24$, whose images are $ad,ab,cb=bc$, respectively. The six possible pairs in $H$ are $ab,ac,ad,bc,bd,cd$; after removing its three edges $ac,bd,cd$, the nonedges are $ab,ad,bc$. These are exactly the images of the nonedges of $G$.

Check: $\phi$ is a bijection because its four images $a,c,d,b$ are distinct and include every element of $W$. The edge and nonedge checks show that adjacency is preserved in both directions, so $G\cong H$. The labels and written edge sets differ, but the path structure has only been relabeled.

Isomorphism Has the Rules of an Equivalence Relation

Isomorphism lets us treat graphs with the same adjacency structure as equivalent, even when their labels differ. The following result verifies that this use of “equivalent” is consistent.

Theorem: Isomorphism of finite simple graphs is reflexive, symmetric and transitive.

Proof. For any graph $G=(V,E)$, the identity map $v\mapsto v$ is a bijection from $V$ to itself. For every pair of distinct vertices $u,v$, $uv\in E$ if and only if $uv\in E$, so the identity is an isomorphism. This proves reflexivity.

Next, suppose $\phi:V(G)\to V(H)$ is an isomorphism. Its inverse $\phi^{-1}:V(H)\to V(G)$ is a bijection. For any distinct $a,b\in V(H)$, write $a=\phi(u)$ and $b=\phi(v)$. The isomorphism condition gives $ab\in E(H)$ if and only if $uv\in E(G)$, which is equivalent to $\phi^{-1}(a)\phi^{-1}(b)\in E(G)$. Thus $\phi^{-1}$ is an isomorphism, proving symmetry.

Finally, suppose $\phi:V(G)\to V(H)$ and $\psi:V(H)\to V(K)$ are isomorphisms. Their composition $\psi\circ\phi$ is a bijection from $V(G)$ to $V(K)$. For distinct $u,v\in V(G)$, $$ uv\in E(G) \quad\Longleftrightarrow\quad \phi(u)\phi(v)\in E(H) \quad\Longleftrightarrow\quad \psi(\phi(u))\psi(\phi(v))\in E(K). $$ So the composition preserves adjacency in both directions and is an isomorphism. This proves transitivity. These arguments also apply when the vertex sets are empty: the empty map is a bijection, and the adjacency condition has no vertex pairs to check. $\square$

Worked Example: Two Components and an Isolated Vertex

Let $G=(V,E)$ have $V=\{1,2,3,4,5,6\}$ and $E=\{12,23,45\}$. Let $H=(W,F)$ have $W=\{a,b,c,d,e,f\}$ and $F=\{ac,cd,be\}$. Define $\phi$ by $1\mapsto a,\ 2\mapsto c,\ 3\mapsto d,\ 4\mapsto b,\ 5\mapsto e,\ 6\mapsto f$.

The six images $a,c,d,b,e,f$ are distinct and make up all of $W$, so $\phi$ is a bijection. The edges map as $12\mapsto ac$, $23\mapsto cd$, and $45\mapsto be$. These are exactly the three edges of $H$. Since $\phi$ maps three distinct edges to the three distinct edges of $H$, there can be no additional edge of $H$ left unmatched; equivalently, each edge $ac,cd,be$ comes from $12,23,45$, respectively.

The components of $G$ are the path on $\{1,2,3\}$, the single edge on $\{4,5\}$, and the isolated vertex $6$. In $H$, they are the path on $\{a,c,d\}$, the single edge on $\{b,e\}$, and the isolated vertex $f$. The map sends each of these components to its counterpart. In particular, $6$ has no incident edge, and its image $f$ also has no incident edge.

Check: The edge list of $G$ has three edges, and the edge list of $H$ has three edges. More importantly, each edge of either graph is accounted for by the displayed bijection, and the only unused vertex in each graph is the isolated one. Therefore adjacency and nonadjacency are preserved, so $G\cong H$.

When Changing an Edge Changes the Structure

A change in the written edge set is not automatically a change in structure: an alternative labeling may still give an isomorphic graph. But some edge changes do produce graphs that cannot be isomorphic. A basic necessary condition follows directly from the definition.

Proposition: If finite simple graphs $G$ and $H$ are isomorphic, then they have the same number of edges.

Proof. Let $\phi:V(G)\to V(H)$ be an isomorphism. It sends every edge $uv$ of $G$ to the edge $\phi(u)\phi(v)$ of $H$. Distinct edges of $G$ have distinct image edges: if their image unordered pairs were equal, injectivity of $\phi$ would imply that their original unordered pairs were equal. Also, every edge of $H$ is the image of an edge of $G$, by the reverse direction of the isomorphism condition and the surjectivity of $\phi$. Thus the edges correspond bijectively, so $|E(G)|=|E(H)|$. $\square$

Worked Example: Adding an Edge to a Three-Vertex Path

Let $G=(V,E)$ have $V=\{1,2,3\}$ and $E=\{12,23\}$. Let $H=(V,F)$ have the same vertex set and $F=\{12,23,13\}$. The only unordered pairs of distinct vertices are $12,13,23$. Thus $G$ has two edges and misses $13$, while $H$ has all three possible edges.

If $G$ and $H$ were isomorphic, the proposition would require their edge counts to agree. But $|E(G)|=2$ and $|E(H)|=3$, so no isomorphism exists. This edge addition has changed the structure, not merely the labels.

Check: Any bijection between the three vertices of $G$ and the three vertices of $H$ sends its two edges to two distinct edges. It cannot account for all three edges of $H$, so the adjacency condition cannot hold in both directions. This agrees with the edge-count argument.

Common Pitfalls

Matching labels is not the same as checking adjacency. For instance, let $G$ have vertices $\{1,2,3\}$ and edges $\{12,23\}$, and let $H$ have vertices $\{a,b,c\}$ and edges $\{ab,bc\}$. The proposed bijection $1\mapsto a,\ 2\mapsto c,\ 3\mapsto b$ sends $12$ to $ac$, which is not an edge of $H$. It fails, even though it is a bijection. The correction is to check each edge under the proposed map: $1\mapsto a,\ 2\mapsto b,\ 3\mapsto c$ sends $12\mapsto ab$ and $23\mapsto bc$, exactly the edges of $H$. This corrected map is an isomorphism.

Do not move the vertices while leaving the old edge list unchanged. Under a relabeling, every edge must be rewritten using the images of both endpoints. If an edge $uv$ is changed to $\phi(u)\phi(v)$, it is the transported edge; if the edge list is altered independently, the result may be a different graph.

Do not confuse “not equal” with “not isomorphic.” Two graphs with different vertex labels or different written edge sets can still have the same structure. Conversely, a bijection between their vertex sets does not prove they are isomorphic; it must preserve adjacency in both directions.

Check Your Understanding

For each question, use the definition of isomorphism and show how adjacency is handled.

Let $G$ have vertices $\{1,2,3\}$ and edges $\{12,23\}$. Construct a relabeled copy on $\{a,b,c\}$ using $1\mapsto c,\ 2\mapsto a,\ 3\mapsto b$.
Why must the map in the definition of an isomorphism be a bijection, rather than just a function that sends edges to edges?
Prove that if $G\cong H$, then $G$ and $H$ have the same number of vertices.
Give a pair of graphs with different written edge sets that are nevertheless isomorphic, and specify an isomorphism.
Explain why adding an edge to a graph does not, by itself, prove that the new graph is nonisomorphic to the original.