# Graph isomorphism

Prove that if $G = (V,E)$ and $G' = (V', E')$ are isomorphic graphs and $\phi: V \to V'$ is an isomorphism, then $d_G(x) = d_G'(\phi(x))$ for all $x \in V$. If, on the other hand, $\phi:V \to V'$ is a bijective mapping satisfying $d_G(x) = d_G'(\phi(x))$ for all $\phi:V \to V'$, then $G$ and $G'$ are not necessarily isomorphic.

I know that two undirected graphs $G = (V, E)$ and $G' = (V', E')$ are isomorphic if there exists a bijective mapping $\phi: V \to V'$, such that $x, y \in V$ are adjacent if and only if $\phi(x)$ and $\phi(y)$ are adjacent. Though, I'm having hard time trying to prove the above statement.

Please note that $d(x)$ is the degree of vertex $x$.

If the first half of the statement is not completely trivial to you, you do not understand graph isomorphisms yet. Look beyond the formal definition into what it means. If $G$ and $G'$ are isomorphic, they're really the same graph, just with their vertices and edges relabelled in some way - but all the connections remain the same. Of course the degree at every vertex remains the same before and after relabelling.
Hint: imagine a graph $V$ that is two chains of several vertices, a horizontal chain and a vertical chain, that meet in the middle in one vertex; a "cross" so to speak. In such a graph, the degrees will be $1$ at the $4$ ends of a cross, $4$ in the center vertex and $2$ everywhere else. Now try to draw a similar, but somewhat different "cross", which has the same number of vertices with the same degrees (so you can match them with a bijective function as required), but they really do not look like the same graph, they're genuinely different. Try to prove that they're not isomorphic.
• $d_G(x)$ is the size of the set $\{y \in V: y \text{ adjacent to } x\}$. $d_G'(\phi(x))$ is the size of the set $\{y \in V': y \text{ adjacent to } \phi(x)\}$. But for every $y$ in $V$ that goes into the first set, $\phi(y)$ in $V'$ goes into the second set, and vice versa, by the definition of $\phi$. Because $\phi$ is also a bijection, it follows that the sets have the same sizes. – AnatolyVorobey Oct 11 '15 at 21:49
• Are you asking for a proof that $d_G(x)=d_G'(ϕ(x))$ on isomorphic graphs, or for an example of non-isomorphic graphs with the same degrees (the second part of the question)? – AnatolyVorobey Oct 13 '15 at 21:31