# Graph Isomorphism when there is a bijection between vertex sets of two graphs.

This is an elementary question, but I have been stuck for a while since I have not been able to prove or disprove this statement: If there exists a bijection f : V (G) → V (H) such that every vertex u ∈ V (G) has the same degree as f(u), then G and H are isomorphic.

But I don't know how to apply this definition:

"Two graphs G = (V,E) and G = (V , E ) are called isomorphic if a bijection f : V → V exists such that {x, y} ∈ E if and only if {f(x), f(y)} ∈ E holds for all x, y ∈ V , x = y. Such an f is called an isomorphism of the graphs G and G . The fact that G and G are isomorphic is written G ∼= G ."

to show that G and H are isomorphic since I have not been able to find a way to show that if {x, y} ∈ E(G), then {f(x), f(y)} ∈ E(H) since the question doesn't give any explicit information about the edges other than the fact that the two graphs have to have the same number (since the degree of each vertex and its image are the same).

My hunch is that the statement is true, but I cannot prove it. Any help would be thoroughly appreciated!

Isomorphisms preserve degree of vertices, but that condition is not sufficient. For a counterexample, let $G$ be $C_6$ (a cycle with $6$ vertices) and $H$ be the union of two copies of $C_3$. Then any bijection between the vertex sets of $G$ and $H$ preserves degree (since the degree of each vertex in either graph is $2$), but $G$ is connected while $H$ is not, so $\not\cong H$.
To see this directly from the definition, suppose $f$ is a bijection from $V(G)$ to $V(H)$. Let $u\in V(G)$ with neighbors $v$ and $w$. Then if $f(u)f(v), f(u)f(w)\in V(H)$, it follows that $f(v)f(w)\in V(H)$. But $vw\notin V(G)$, so $f$ is not an isomorphism.