2 added 3 characters in body

The other answers have treated the case of finite graphs, but there is something interesting to say about infinite graphs as well.

For example, we might consider the case of computable graphs. A graph is computable if it has a computable edge relation on the vertex set of natural numbers. It is quite natural to inquire of isomorphic computable graphs, whether they have a computable isomorphism.

Question. If $G$ and $H$ are computable graphs and isomorphic, must there be a computable isomorphism?

I hope you will find it interesting to learn that the answer is No. To see this, let me describe two isomorphic graphs, which will both be trees of height 2, having infinitely many leaves on level $1$ and infinitely many leaves on level $2$, but no splitting except at the root. On the one hand, we can easily build a computable such graph $G$, by using $0$ as the root, the remaining even numbers as the level $1$ nodes, and giving exactly the multiples of $4$ a successor on level $2$, using the odd numbers. Next, let me describe another computable presentation $H$ of this graph. We again use $0$ as the root and the remaining even numbers $2n$ as the level one nodes. But this time, we give $2n$ a successor, using the $k^{\rm th}$ odd number in the construction, only if program $n$ halts on input $0$ in less than time $k$. The graphs $G$ and $H$ are certainly isomorphic, because of their trivial form, but there can be no computable isomorphism between them, since any isomorphism would have to send the node $2n$ in $H$ either to a multiple of $4$ or not, and this would reveal whether it gets a successor in $G$, which would in turn tells us whether the program $n$ halts or not, solving the halting problem. So there can be no such computable isomorphism. QED

The argument generalizes to oracles. That is, for any Turing degree $d$, there are isomorphic graphs that are computable from oracle $d$, but no isomorphism between them is computable from $d$. Thus, in the infinite case, one answer to your question is that you cannot compute the isomorphism of isomorphic graphs $G$ and $H$ just knowing $G$ and $H$. The isomorphism may simply have a greater Turing degree.

More generally, this article by Csima, Khoussainov and Liu investigates the class of computably categorical graphs, the graphs $G$ that have the property that any two computable presentations of $G$ should be computably isomorphic.

I discuss the issues of computable categoricity in this MO answer, which asked whether there could be equivalence without us being able to calculate it, a question for which the subject of computable model theory provides numerous answers.

And there is more to say when one moves to uncountable graphs...

1

The other answers have treated the case finite graphs, but there is something interesting to say about infinite graphs as well.

For example, we might consider the case of computable graphs. A graph is computable if it has a computable edge relation on the vertex set of natural numbers. It is quite natural to inquire of isomorphic computable graphs, whether they have a computable isomorphism.

Question. If $G$ and $H$ are computable graphs and isomorphic, must there be a computable isomorphism?

I hope you will find it interesting to learn that the answer is No. To see this, let me describe two isomorphic graphs, which will both be trees of height 2, having infinitely many leaves on level $1$ and infinitely many leaves on level $2$, but no splitting except at the root. On the one hand, we can easily build a computable such graph $G$, by using $0$ as the root, the remaining even numbers as the level $1$ nodes, and giving exactly the multiples of $4$ a successor on level $2$, using the odd numbers. Next, let me describe another computable presentation $H$ of this graph. We again use $0$ as the root and the remaining even numbers $2n$ as the level one nodes. But this time, we give $2n$ a successor, using the $k^{\rm th}$ odd number in the construction, only if program $n$ halts on input $0$ in less than time $k$. The graphs $G$ and $H$ are certainly isomorphic, because of their trivial form, but there can be no computable isomorphism between them, since any isomorphism would have to send the node $2n$ in $H$ either to a multiple of $4$ or not, and this would reveal whether it gets a successor in $G$, which would in turn tells us whether the program $n$ halts or not, solving the halting problem. So there can be no such computable isomorphism. QED

The argument generalizes to oracles. That is, for any Turing degree $d$, there are isomorphic graphs that are computable from oracle $d$, but no isomorphism between them is computable from $d$. Thus, in the infinite case, one answer to your question is that you cannot compute the isomorphism of isomorphic graphs $G$ and $H$ just knowing $G$ and $H$. The isomorphism may simply have a greater Turing degree.

More generally, this article by Csima, Khoussainov and Liu investigates the class of computably categorical graphs, the graphs $G$ that have the property that any two computable presentations of $G$ should be computably isomorphic.

I discuss the issues of computable categoricity in this MO answer, which asked whether there could be equivalence without us being able to calculate it, a question for which the subject of computable model theory provides numerous answers.

And there is more to say when one moves to uncountable graphs...