Graph Isomorphism

In graph theory, an isomorphism between two graphs G and H is a bijection between their vertex sets that preserves adjacency, so it can be described as an edge-preserving bijection, following the general principle that isomorphisms preserve structure. Two graphs between which such a bijection exists are called isomorphic, and a bijection of this kind from a graph to itself is called an automorphism of that graph. Graph isomorphism is an equivalence relation on graphs, dividing all graphs into equivalence classes called isomorphism classes, and whether the graph isomorphism problem, deciding whether two graphs are isomorphic, can be solved in polynomial time is one of the major open questions in computer science.