Section 7.4 Isomorphism
Informally, we can say that an isomorphism is a relation of sameness between graphs. Let’s say that the graphs \(G = (V, E)\) and \(G' = (V', E')\) are isomorphic if there exists a bijection \(f: V \rightarrow V'\) such that \(\{u, v\} \in E \Leftrightarrow \{f(u), f(v)\} \in E'\text{.}\)
This means there is a bijection between the set of vertices such that every time two vertices determine an edge in the first graph, the image of these vertices by the bijection also determines an edge in the second graph, and vice versa. Essentially, the two graphs have the same structure, but the vertices are labeled differently.
The sage
is_isomorphic() method can be used to check if two graphs are isomorphic. The method returns True if the graphs are isomorphic and False if the graphs are not isomorphic.The invariants under isomorphism are conditions that can be checked to determine if two graphs are not isomorphic. If one of these fails then the graphs are not isomorphic. If all of these are true then the graph may or may not be isomorphic. The three conditions for invariants under isomorphism are:
\begin{equation*}
G = (V, E) \text{ is connected iff } G' = (V', E') \text{ is connected}
\end{equation*}
\begin{equation*}
|V| = |V'| \text{ and } |E| = |E'|
\end{equation*}
\begin{equation*}
\text{degree sequence of } G = \text{ degree sequence of } G'
\end{equation*}
To summarize, if one graph is connected and the other is not, then the graphs are not isomorphic. If the number of vertices and edges are different, then the graphs are not isomorphic. If the degree sequences are different, then the graphs are not isomorphic. If all three invariants are satisfied, then the graphs may or may not be isomorphic.
Let’s define a function to check if two graphs satisfy the invariants under isomorphism. Make sure you run the next cell to define the function before using the function.
If we use
invariant_under_isomorphism on the \(C\) and \(D\text{,}\) the output will let us know that the graphs may or may not be isomorphic. We can use the is_isomorphic() method to check if the graphs are definitively isomorphic.Let’s construct a different pair of graphs \(A\) and \(B\) defined as follow
This time, if we apply
invariant_under_isomorphism function on \(A\) and \(B\text{,}\) the output will show us that they are not isomorphic.
