Graph Isomorphism

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.