 Graph non-isomorphism

Two graphs exhibit 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 $\varphi :V_G\to V_H$ satisfyingfor 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.^[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.