Graph Isomorphism Problem

Definition

Graph Isomorphism Problem

The graph isomorphism problem is the decision problem of determining whether two finite graphs have the same structure up to a relabelling of their vertices.

Instance: two finite graphs $G=(V_G,E_G)$ and $H=(V_H,E_H)$.

Question: does there exist a bijection $f:V_G\to V_H$ such that, for every $u,v\in V_G$,

$$\{u,v\}\in E_G⟺\{f(u),f(v)\}\in E_H?$$

Equivalently, the question is whether $G\cong H$ under a graph isomorphism. The corresponding language is

$$\mathrm{GI}=\{⟨G,H⟩\mid G\cong H\}.$$