Graph isomorphism

Bijection between the vertex set of two graphs

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f : V ( G) → V ( H) {\displaystyle f\colon V(G)\to V(H)} such that any two vertices u and v of G are adjacent in G if and only if f ( u) {\displaystyle f(u)} and f ( v) {\displaystyle f(v)} are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic, often denoted by G ≃ H {\displaystyle G\simeq H} . In the case when the isomorphism is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the isomorphism is called an automorphism of G. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes.

From Wikipedia, under CC BY-SA. More on occurri.