(adsbygoogle = window.adsbygoogle || []).push({}); 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(V_{g},E_{g}), and the right graph be H(V_{h},E_{h})

Since the graph is isomorphic we know:

1) There is a bijective functionffrom V_{g}to V_{h}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 V_{g}.

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 V_{g}to V_{h}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 V_{g}).

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Proving a (known isomorphic) graph is isomorphic

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**