# isomorphisms question

• Jun 5th 2011, 02:23 AM
mathgirl1
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.
• Jun 5th 2011, 06:03 AM
emakarov
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.
• Jun 5th 2011, 03:00 PM
mathgirl1
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.
• Jun 5th 2011, 03:16 PM
emakarov
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.
• Jun 5th 2011, 03:25 PM
mathgirl1
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?
• Jun 5th 2011, 03:28 PM
emakarov
Quote:

So this is a counterexample?
Yes, for the first function.
• Jun 5th 2011, 03:34 PM
mathgirl1
Thanks again emakarov.