1. The problem statement, all variables and given/known data Graph: Included as an upload or: http://mgh-images.s3.amazonaws.com/9780073383095/4944-10.3-43IE1.png Given: The graph is isomorphic. Prove that it is indeed isomorphic. 2. Relevant equations 3. The attempt at a solution Let the left graph be G(Vg,Eg), and the right graph be H(Vh,Eh) Since the graph is isomorphic we know: 1) There is a bijective function f from Vg to Vh with the property that a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in Vg. 2) The graphs share the same number of vertices, edges, and degree sequence. And then from here I'm lost. I know that I have to formulate a bijective function from Vg to Vh which is easy since the cardinality of vertices are the same. The issue I have is being sure that this bijective function has the second property (a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in Vg). Given that I know the graph is isomorphic, is there any methodical approach to this? I tried messing around with various functions for about 3 hours before I found one that worked. However, there was no method to my madness beyond trial and error. With simpler graphs, I can kind of tell how the bijective function should be formed because I can visualize a form of the graph that both graphs fit into. For example I can see that a star -- like in graph g -- can unfold into a cycle of 5 vertices (or a pentagon). But as these get more complex I can't. Even breaking the graph into more manageable chunks doesn't seem to help. I'm worried that I won't have enough time to figure these out on a test. Thanks.