# Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial.

Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for $i\in\{1,2\}$ are isomorphic, in time quasipolynomial in $v=|V_i|$.

Did Babai actually show how to find an element $\pi\in S_v$ that permutes the vertices of $G_1$ to $G_2$, or is the certificate merely an existence-statement?

If an oracle tells me that $G_1$ and $G_2$ are isomorphic, do I still need to look through all $v!$ permutations of the vertices?

I ask because I also think about knot equivalence. As far as I know, it's not known to be, but say detecting the unknot were in $\mathsf{P}$. Actually finding a sequence of Reidemeister moves that untie the knot might still take exponential time...

These problems are polynomially equivalent. Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are. Attach a clique of size $n+1$ to an arbitrary vertex of each graph. Test whether the resulting graphs are isomorphic or not. If they are, then we can conclude that there's an isomorphism that maps the respective vertices to each other, thus we can delete them. By repeating this test $n$ times, we can find (a possible) image for any vertex. After this, we attach another clique, this time of size $n+2$ to a (different) arbitrary vertex of each original graph, and proceed as before, etc. Eventually, we'll end up with two graphs that are isomorphic, with cliques of size $n+1,\ldots n+n$ hanging from their vertices, which makes the isomorphism unique.