1
$\begingroup$

I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ What is graph isomorphism for you? Please add to your post a formal description. $\endgroup$ – Yuval Filmus Dec 2 at 23:11
7
$\begingroup$

You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic.

Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$.

You take it from here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy