An isomorphism of graphs and is a bijection between the vertex sets of and
such that any two vertices and of are adjacent in iff and are adjacent in .
This kind of bijection is commonly described as “edge-perserving bijection”.
If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as .
In case when the bijection is a maping of a graph onto itself, i.e. when and are one and the same graph, the bijection is called an automorphism of .
Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalance classes.