1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about isomorphism (Graph Theory)

  1. Jan 5, 2016 #1
    1. The problem statement, all variables and given/known data
    1. up to isomorphism, there is only one 2-regular graph on 5 vertices.

    2. Relevant equations


    3. The attempt at a solution
    I am still working on the problem, but I don't understand what up to isomorphism means. Does it mean without considering isomorphism?. I just need help with that. Considering isomorphism, the first thing that comes to mind is a pentagon. The complement of this graph would also be a 2-regular on 5 vertices. Therefore, the original statement would be false.
     
    Last edited: Jan 5, 2016
  2. jcsd
  3. Jan 5, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The proposition means 'All 2-regular graphs on five vertices are isomorphic to one another'.
    Correct
    No, because the complement is isomorphic to the original.
     
  4. Jan 5, 2016 #3
    so if two graphs are isomorphic, it doesn't mean that they are different?
     
  5. Jan 5, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Different graphs can be isomorphic. Here are two different but isomorphic graphs on three points:

    { {1,2} }
    { {2,3} }

    The isomorphism is the function { (1,2), (2,3), (3,1) }
     
  6. Jan 5, 2016 #5
    The way to get all 2-regular graphs on 5 vertices would be by making permutations among vertices and calculating the complement of the original graph. All this leads to being isomorphic to one another. Is there any other way to get other isomorphic graphs?. Am I taking the right approach to solve this problem?. I also want to add that the only way to make a 2-regular graph on 5 vertices is a pentagon and the complement of the pentagon. I think. Is there another way?
     
  7. Jan 6, 2016 #6

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    @TheMathNoob You don't have to take complements. Permutations will cover all possible cases. That is, the set of isomorphs of a graph G is simply the set of graphs obtained by permuting the vertices and edges of G.
    By the way, the complement of a pentagon is topologically a pentagon. You just need to move the vertices around a bit after taking the complement and you'll end up with a pentagon with permuted vertex labels.

    You are correct that all 2-regular graphs on five vertices are (topologically equivalent to) pentagons. Have you made any progress on working out how to prove that?
     
  8. Jan 6, 2016 #7
    Hi andrw, thank you for the help. I am still working on the problem. I need to know what you mean with topologically equivalent to.
     
  9. Jan 6, 2016 #8

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The layperson's description is that two shapes are topologically equivalent if one can be transformed into the other by continuous deformation. There is no cutting or gluing allowed, but you can rotate, translate and bend as much as you like.
     
  10. Jan 6, 2016 #9
    This is so far what I got

    Proof

    Let Z be a set of 5 vertices v1,v2,v3,v4,v5. A 2-regular graph on 5 vertices is a graph in which the degree of every vertex is 2.
    If we start linking every vertex with every other vertex in the set in a way that the degree of the vertices can be 2, we will realize that the graph is always equivalent to a pentagon.

    Pick V1
    In this case we can just link V1 to any vertex hence there is currently just one vertex in the graph. Let’s do V1V2.

    Pick V2
    In this case we can just link V2 to remaining vertices because V2 is already linked to V1. Let’s do V2V3.

    Pick V3
    In this case we can’t link V3 to V1 because the remaining vertices would have to have a degree of just 1. And we can’t like V3 to V2 because they are already linked, so the best option for V3 is any remaining vertex. Let’s do V3V4

    Pick V4
    In this we can’t link V4 to V1 and V2 because the remaining vertex would have to have a degree of 0 and V3 because they are already linked. The best option for V4 would be V5. Let’s do V4V5.

    Pick V5
    This is the last vertex and the only way to make this graph 2 regular would be by linking V5 to V1.

    We can just do the same process in any order you want and the outcome will always be a pentagon. Permuting vertices in a pentagon just creates isomorphic relations among themselves therefore there is just one 2-regular graph on 5 vertices.
     
    Last edited: Jan 6, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof about isomorphism (Graph Theory)
  1. Set theory proof (Replies: 1)

  2. Graph Isomorphism (Replies: 12)

Loading...