Two graphs are isomorphic if there is a bijection between their vertices

Question

"Show that two simple graphs $G$ and $H$ are isomorphic if and only if there is a bijection $\theta:V(G)\to V(H)$ such that $uv\in E(G)$ if and only if $\theta(u)\theta(v)\in E(H)$."

If I understand correctly this basically means that there should exist a bijection between their vertices that also preserves the edges. However, I'm not sure how to show this formally.

I was thinking maybe $uv\in E(G)$ iff $\theta(u)\theta(v)\in E(H)$ means that every edge in G has a corresponding edge in H after mapping the vertices, and vice versa. Therefore there exists a bijection between the edges of $G$ and $H$ and they are isomorphic.

Is this right? Is there a better or more formal way to express this? Thanks!

Answer 1

$(\rightarrow)$: If $ G $ and $ H $ are isomorphic, then there exists a bijection $ \theta: V(G) \rightarrow V(H) $ such that $ uv \in E(G) $ if and only if $ \theta(u)\theta(v) \in E(H) $*

Let $ \phi: E(G) \rightarrow E(H) $ be the function defined by $ \phi(uv) = \theta(u)\theta(v) $. Since $ \theta $ is a bijection, $ \phi $ is well-defined and is also a bijection. This means that each edge in $ G $ is mapped to a unique edge in $ H $ under $ \phi $, and vice versa.

$(\leftarrow)$: If there is a bijection $ \theta: V(G) \rightarrow V(H) $ such that $ uv \in E(G) $ if and only if $ \theta(u)\theta(v) \in E(H) $, then $ G $ and $ H $ are isomorphic.*

Let $ \phi: E(G) \rightarrow E(H) $ be the function defined by $ \phi(uv) = \theta(u)\theta(v) $. Again, since $ \theta $ is a bijection, $ \phi $ is well-defined and is also a bijection. This implies that each edge in $ G $ is mapped to a unique edge in $ H $ under $ \phi $, and vice versa.

Now, define $ \psi: V(G) \rightarrow V(H) $ by $ \psi(u) = \theta(u) $. Since $ \theta $ is a bijection, $ \psi $ is also a bijection. Moreover, $ \psi $ preserves adjacency, as $ uv \in E(G) $ if and only if $ \phi(uv) = \theta(u)\theta(v) \in E(H) $. So, $ G $ and $ H $ are isomorphic.

In summary, the key is to establish a bijection between the edges of $ G $ and $ H $ that preserves adjacency. The proof involves showing that such a bijection implies isomorphism in both directions.