= Graph non-isomorphism
Two <graphs> exhibit \b[graph non-isomorphism] when no <bijection> of their vertex sets preserves and reflects adjacency. For finite <simple graphs> $G=(V_G,E_G)$ and $H=(V_H,E_H)$, this means there is no bijection $\phi:V_G\to V_H$ satisfying
$$
\{u,v\}\in E_G\quad\Longleftrightarrow\quad\{\phi(u),\phi(v)\}\in E_H
$$
for every pair of distinct vertices. Changing vertex names or drawing positions cannot establish non-isomorphism; the adjacency structure must differ.
A <graph invariant> is a property preserved by <graph isomorphism>. Different numbers of vertices, edges or <connected components of a graph> immediately prove non-isomorphism. Equal values of one invariant need not prove isomorphism.
For an original example, let $G$ be the six-vertex <cycle graph> with edges $12,23,34,45,56,61$, and let $H$ be the <disjoint union of graphs> consisting of triangles $123$ and $456$. Both have six vertices, six edges and <degree sequence> $(2,2,2,2,2,2)$. Nevertheless, $G$ is a <connected graph>, whereas $H$ has two connected components. Any adjacency-preserving bijection transports a path to a path, so it would have to preserve connectedness. No such bijection exists. The common degree sequence is therefore an incomplete isomorphism test.
Finite exhaustive checking provides a direct decision procedure: if the vertex counts agree at $n$, examine each of the $n!$ possible bijections and test adjacency. If every bijection fails, the graphs are non-isomorphic. More efficient procedures can avoid enumerating all bijections; this simple procedure explains the logical criterion, rather than a practical performance bound.
Software tests also require a decision about what belongs to the structure. NetworkX's `is_isomorphic` ignores node and edge attributes by default; matching functions can require them to agree.<is_isomorphic documentation by NetworkX>[node_match, edge_match and Examples]{ref} Two differently colored copies of the same uncolored graph can thus be isomorphic as simple graphs but non-isomorphic under a color-preserving requirement. The intended graph category must be specified before interpreting a negative result.
Back to article page
