Results 1 to 4 of 4

Math Help - Are any of the following graphs isomorphic?

  1. #1
    r45
    r45 is offline
    Junior Member
    Joined
    Mar 2010
    Posts
    35

    Are any of the following graphs isomorphic?

    Hi there,

    I am trying to do this question from my textbook. I couldn't reproduce the diagrams so I've just taken a photo of it.




    As far as I know there's no simple way of checking, it's generally done by intuition and inspection. I know there are ways of showing that two graphs are NOT isomorphic (eg different degree sequence, different number of edges etc.) but I can't apply those here.

    All 3 graphs have 10 vertices, 15 edges, and every vertex has degree 3. Thus they all have (3, 3, 3, 3, 3, 3, 3, 3, 3, 3) - I know that generally having the same degree sequence doesn't prove isomorphism, but does it in this case? I have a suspicion that if two graphs have degree sequences of (k, k, k, ...., k) then they are isomorphic, is that right?

    Another approach I took was to find the adjacency matrices of each graph. This took some doing. My book says that if 2 graphs have similar adjacency matrices then they are isomorphic. However, I have 3 10x10 matrices all with 0s and 1s as their entries. They all have determinant 0, trace 0. Is this sufficient to show they are similar?

    It is my belief that all 3 pairs of these graphs are isomorphic, but the second part of the question asks me to find an isomorphism - how on earth would I do that?

    Many thanks,
    R
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    It looks to me as though in the left graph (the Petersen graph) every cycle has length 5. But the middle graph has a 6-cycle (the outer circle), and the right graph has some 4-cycles (but no 6-cycles that I can see). So my guess is that all three graphs are nonisomorphic. But I don't know a quick or convincing way to prove that.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by Opalg View Post
    It looks to me as though in the left graph (the Petersen graph) every cycle has length 5. But the middle graph has a 6-cycle (the outer circle), and the right graph has some 4-cycles (but no 6-cycles that I can see). So my guess is that all three graphs are nonisomorphic. But I don't know a quick or convincing way to prove that.
    In fact, there is a 6 cycle in Petersen graph - see the attachment and check 1-1'-3'3-4-5.

    The attachment should show you that 1 and 2 are isomorphic.

    They are not isomorphic to the 3rd one, since it contains 4-cycle and Petersen's graph does not. (Every vertex of Petersen graph is "equivalent". To find a cycle, you would have to find two paths of length 2 starting in the same vertex and ending in the same vertex. If you try all 3 neighbors of some vertex, you see, that no two of them have a common neighbor.)

    EDIT:
    http://images.google.com/images?q=petersen+graph leads to more planar drawings of Petersen graph, this one is containing two of your graphs:
    http://www.imada.sdu.dk/~btoft/GT200...ddings_800.gif
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  4. #4
    r45
    r45 is offline
    Junior Member
    Joined
    Mar 2010
    Posts
    35
    Brilliant, many thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. isomorphic graphs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: June 4th 2011, 08:25 PM
  2. Isomorphic Connected Graphs
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 12th 2010, 05:37 PM
  3. Pairwise non-isomorphic regular graphs!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 11:22 AM
  4. Are all regular graphs isomorphic?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 25th 2009, 07:29 AM
  5. Isomorphic Graphs- hw help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 21st 2008, 05:49 PM

Search Tags


/mathhelpforum @mathhelpforum