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.

The second half is the non-trivial one. You need to draw two very similar undirected graphs, which you can match vertex by vertex with the same degree, but edges will not match no matter how you try to match the vertices. These cannot be very very simple graphs, you have to be a little sophisticated.

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.

  • $\begingroup$ The first part is clear to me that they are same graphs. Though, I'm having a bit hard time proving it mathematically. $\endgroup$ – user72151 Oct 11 '15 at 21:45
  • $\begingroup$ $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. $\endgroup$ – AnatolyVorobey Oct 11 '15 at 21:49
  • $\begingroup$ I still didn't manage to come up with such a prove. Can you show me the proof? $\endgroup$ – user72151 Oct 13 '15 at 21:06
  • $\begingroup$ 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)? $\endgroup$ – AnatolyVorobey Oct 13 '15 at 21:31
  • $\begingroup$ For the first part, regarding the equal degrees, I used your previous comment, isn't it a sufficient proof? And for the second part, I need an example of non-isomorphic graphs with the same degree, and a bit more about how can it be proved from the examples. $\endgroup$ – user72151 Oct 13 '15 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy