Definition: Isomorphic Undirected Graphs

Two graphs \(G_1(V_1,E_1,\gamma_1)\) and \(G_2(V_2,E_2,\gamma_2)\) are isomorphic, written as \(G_1\equiv G_2\), if \(G_1\) can be transformed to \(G_2\) (and vice versa) by relabelling the vertices, without changing adjacent vertices and edges.

Formally, \(G_1\equiv G_2\) if and only if there exist two bijective functions, a relabelling function \(\rho : V_1 \to V_2\) and an edge transformation function \(\epsilon : E_1 \to E_2\) and such that

\[\rho(\gamma_1(e))=\gamma_2(\epsilon(e))\quad\forall e\in E_1.\]

This is equivalent to a transformation, in which the number of edges joining each pair of vertices in \(G_1\) is equal to the number of edges joining the corresponding pair of vertices in \(G_2\).

Note: In the left side of the equation, \(\rho(\gamma_1(e))\) means that we relabel the end vertices \(\gamma_1(e)\) of given edge \(e\) in the first graph \(G_1\), obtaining in the right side of the equation the corresponding end vertices \(\gamma_2(\epsilon(e))\) of an edge \(\epsilon(e)\) of the second graph \(G_2\).



In the above figure, the graphs \(G_1\) and \(G_2\) are not the same, but they are isomorphic, since we can find two bijective functions \(\rho : V_1 \to V_2\) and \(\epsilon : E_1 \to E_2\) defined by

Definition of \(\rho\):

\(v\in V_1\) \(\rho(v)\in V_2\)
\(a\) \(u\)
\(b\) \(x\)
\(c\) \(v\)
\(d\) \(w\)

Definition of \(\epsilon\): \(e\in E_1\)|\(\epsilon(e)\in E_2\) \(e_1\)| \(f_1\) \(e_2\)| \(f_2\) \(e_3\)| \(f_3\) \(e_4\)| \(f_4\) \(e_5\)| \(f_5\) \(e_6\)| \(f_6\) \(e_7\)| \(f_7\)

such that all adjacencies in the digraphs are preserved, like demonstrated in the following table:

|\(e\)|\(\gamma_1(e)\)|\(\rho(\gamma_1(e))\)|\(\gamma_2(\epsilon(e))\)|\(\epsilon(e)\)| \(e_1\)| \(\{a,b\}\)| \(\{u,x\}\)| \(\{u,x\}\)| \(f_1\) \(e_2\)| \(\{a,b\}\)| \(\{u,x\}\)| \(\{u,x\}\)| \(f_2\) \(e_3\)| \(\{a,b\}\)| \(\{u,x\}\)| \(\{u,x\}\)| \(f_3\) \(e_4\)| \(\{a,c\}\)| \(\{u,v\}\)| \(\{u,v\}\)| \(f_4\) \(e_5\)| \(\{b,d\}\)| \(\{x,w\}\)| \(\{x,w\}\)| \(f_5\) \(e_6\)| \(\{c,d\}\)| \(\{v,w\}\)| \(\{v,w\}\)| \(f_6\) \(e_7\)| \(\{d\}\)| \(\{w\}\)| \(\{w\}\)| \(f_7\)

Thank you to the contributors under CC BY-SA 4.0!




  1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000
  2. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition