---
title: "Graph Isomorphism is in NP"
type: concept
source: https://www.jemoka.com/posts/kbhgraph_isomorphism_is_in_np/
confidence: high
status: active
---

Recall the definition of graph : if you can relabel \(G\) to get \(G&rsquo;\), that they are the same up to relabling.
\begin{equation} \text{GISO} = \qty {\langle G,G&rsquo; \rangle \mid G \cong G&rsquo;} \end{equation}
Because the prover can just give the relabeling.
