1. ## isomorphisms question

Hi,

The definition of an isomorphism is a bijection between the sets of G and H

f: V(G) -> V(H)
such that any two vertices u and v of G are adjacent in G if and only if f(u) and f(v) are adjacent in H.

They following 3 functions are not isomorphisms but I need to provide one counterexample to the property above in each case.

ImageShack&#174; - Online Photo and Video Hosting

Thanks in advance for any help.

2. My guess is that these functions refer to graphs from a previous thread, but when I follow the link to ImageShack in that thread, i don't see the graphs anymore.

Anyway, I would go through every edge in the source graph and see if it preserved by the function, marking the corresponding edge in the target graph. If all source edges are preserved and no target edge is unmarked, then the function is an isomorphism.

3. Thanks emakarov.
Here are the graphs: ImageShack&#174; - Online Photo and Video Hosting
So a counterexample would be:
For the 1st table: Let u=1,v=2 -> f(u)=a,f(v)=b. And 1,2 and a,b are both adjacent in there respective graphs? And I know those two graphs are not isomorphic, so this would be a counterexample.

4. If you look at a cat and a pigeon, the fact that both of them have a head is not an evidence that they are different species. Such evidence could be that a cat has front paws while a pigeon had wings instead.

Consider vertices 9 and 10.

5. Oh yes, thanks emakarov. So if we let u=9,v=10 -> f(u)=i,f(v)=j, and 9 and 10 are adjacent in graph 1 but i and j are not adjacent in graph 2. So this is a counterexample?

6. So this is a counterexample?
Yes, for the first function.

7. Thanks again emakarov.