LearnMathOnline

Two graphs with different drawings may have the same graph properties. How do we know two graphs are essentially the same but with different labelings of vertices?

Definition (Isomorphism). Two simple graphs \(G=(V_G,E_G)\) and \(H=(V_H,E_H)\) are isomorphic, denoted by \(G\cong H\), if there is a bijection (one-to-one and onto function) \(f:V_G\to V_H\) such that \(\{a,b\}\in E_G\) if and only if \(\{f(a),f(b)\}\in E_H\). Such a function \(f\) is called an isomorphism between \(G\) and \(H\). If there is an isomorphism between \(G\) and \(H\), they are called isomorphic. Two graphs are nonisomorphic if they are not isomorphic.

Remark. A property of graphs preserved under graph isomorphism are called a graph invariant. For example, the number of vertices and edges, degree sequence, connectedness, vertex connectivity, chromatic number are graph invariants.

Problem. Determine whether \(G\) and \(H\) are isomorphic. Find an isomorphism or provide a rigorous argument that none exists.

Solution. Consider the bijection \(f:V(G)\to V(H)\) such that \[f(v_1)=u_1,\;f(v_2)=u_3,\;f(v_3)=u_5,\;f(v_4)=u_2, \text{ and } f(v_5)=u_4.\] It can be verified that \(\{v_i,v_j\}\in E(G)\) if and only if \(\{f(v_i),f(v_j)\}\in E(H)\). Thus \(G\cong H\), i.e., \(G\) and \(H\) are isomorphic.

Problem. Determine whether \(G\) and \(H\) are isomorphic. Find an isomorphism or provide a rigorous argument that none exists.

Solution. Suppose there is an isomorphism \(f:V(G)\to V(H)\). Since \(\operatorname{d}(v_1)=1\) and \(\operatorname{d}(u_1)=\operatorname{d}(u_7)=\operatorname{d}(u_8)=\operatorname{d}(u_6)=1\), \(f(v_1)\) is one of \(u_1,u_6,u_7\), and \(u_8\). Note that \(v_1\) is adjacent to \(v_2\) which has degree 2. But none of \(u_1,u_6,u_7\), and \(u_8\) is adjacent to a degree 2 vertex. Thus there is no such isomorphism \(f:V(G)\to V(H)\), i.e., \(G\) and \(H\) are not isomorphic. Note that \(G\) and \(H\) have the same degree sequence \((3,3,2,2,1,1,1,1)\).

Definition. A permutation matrix of order \(n\) is a binary matrix obtained from the identity matrix \(I_n\) by permuting (i.e., rearranging) its rows.

Theorem. Two simple graphs \(G\) and \(H\) are isomorphic if and only if \(A_H=PA_GP^T\) for some permutation matrix \(P\).

For the above isomorphic graphs \(G\) and \(H\), \(A_H=PA_GP^T\), i.e., \[\left[\begin{array}{ccccc} 0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&0&1\\ 1&1&0&0&0\\ 0&1&1&0&0 \end{array}\right] =\left[\begin{array}{ccccc} 1&0&0&0&0\\ 0&0&0&1&0\\ 0&1&0&0&0\\ 0&0&0&0&1\\ 0&0&1&0&0 \end{array}\right] \left[\begin{array}{ccccc} 0&1&0&0&1\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 1&0&0&1&0 \end{array}\right] \left[\begin{array}{ccccc} 1&0&0&0&0\\ 0&0&1&0&0\\ 0&0&0&0&1\\ 0&1&0&0&0\\ 0&0&0&1&0 \end{array}\right]. \] Note that \(P=\left[\begin{array}{ccccc} 1&0&0&0&0\\ 0&0&0&1&0\\ 0&1&0&0&0\\ 0&0&0&0&1\\ 0&0&1&0&0 \end{array}\right]\) is obtained from \(I_5\) by permuting rows \(1,2,3,4,5\) to rows \(1,3,5,2,4\) respectively which is seen from the isomorphism \(f:V(G)\to V(H)\): \[f(v_1)=u_1,\;f(v_2)=u_3,\;f(v_3)=u_5,\;f(v_4)=u_2, \text{ and } f(v_5)=u_4.\]

Remark. There are \(n!\) possible isomorphisms between two graphs on \(n\) vertices. The graph isomorphism problem is to determine whether two given graphs on \(n\) vertices are isomorphic. The graph isomorphism problem is a famous problem in computational complexity and it is not known whether it is solvable in polynomial time (i.e., the number of steps is a polynomial of \(n\)).