I have a (hopefully simple, maybe dumb) question on Babai's landmark [paper](https://arxiv.org/abs/1512.03547) 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...