Results 1 to 7 of 7

Math Help - isomorphisms question

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    20

    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® - Online Photo and Video Hosting

    I am slightly confused here. Could someone please help me here.

    Thanks in advance for any help.
    Last edited by mathgirl1; June 5th 2011 at 02:14 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Thanks emakarov.
    Here are the graphs: ImageShack® - 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2011
    Posts
    20
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    So this is a counterexample?
    Yes, for the first function.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Thanks again emakarov.
    Last edited by mathgirl1; June 5th 2011 at 07:32 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Isomorphisms
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 11th 2011, 10:56 PM
  2. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 20th 2011, 02:14 PM
  3. Isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 28th 2010, 09:03 PM
  4. Z2 + Z2 + Z3 isomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 2nd 2008, 06:34 PM
  5. [SOLVED] Isomorphisms question
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 28th 2007, 03:21 AM

Search Tags


/mathhelpforum @mathhelpforum