I need to prove that two graphs (say, H and G) which are isomorphic and their vertices have the same degree.
So far, I have the summation of the degrees across all vertives is 2|E| and since if two graphs are isomorphic, then they must have the same number of edges. Therefore, each corresponding vertex in H and G must have the same degree. Is this sufficient? Thanks!
Best Answer
That is not sufficient, because the last implication doesn't hold. $C_4$, the cycle on four vertices has 4 edges, as does a triangle with one additional edge sticking out from one of it's vertices. However those two graphs are not isomorphic, and the degrees fail to line up. In the later graph, there is a vertex of degree 3 and a vertex of degree 1, but in $C_4$ all vertices have degree 2. This approach is unlikely to work, because it doesn't use the "full power" of isomorphism.
Consider this approach: Let $\varphi:G\to H$ be an isomorphism. Then for $g,g'\in G$, we have that $$g\sim g'\iff \varphi(g)\sim\varphi(g')$$ This is the property you want to use to solve the problem. Try picking a vertex,$g\in G$ and assuming that $\varphi(g)$ and $g$ have different degrees and see what happens. Then take a vertex $h\in H$ and assume that $h$ and $\varphi^{-1}(h)$ have different degrees and see what happens. In both cases you should quickly get a contradiction.