1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

Graph Isomorphism

  1. Dec 6, 2015 #1
    1. The problem statement, all variables and given/known data
    Are the 2 graphs isomorphic?

    2. Relevant equations

    3. The attempt at a solution
    Both have same vertices, edges, set of degrees. But I failed to prove isomorphism by adjacency matrices.
  2. jcsd
  3. Dec 6, 2015 #2
    Hi Sarah00:

    Did you create the G1 and G2 matrices?
    What techniques do you know regarding showing that two matrices demonstrate isomorphism?

  4. Dec 6, 2015 #3
    Thanks for your reply.
    What I did is I wrote the degree above each vertex.
    Then I form a path going to all vertices.
    After that, I try to map it with the other graph.

    However, this was challenging.
    4 vertices have degree 4
    2 vertices degree 3

    I tried all possibilities to prove it is isomorphic

    I don't think they are isomorphic.. are they??
  5. Dec 6, 2015 #4
    Hi Sarah:

    I did not complete a vertex to vertex mapping, but I mapped 5 of the 7 before I had to stop to do chores. My guess is that the two graphs are isomorphic.
    If you don't want to work with matrices, then I suggest that you map one at a time each G1 vertex, v1-v7, onto a G2 vertex,, a-g. I recommend starting with the lower count vertices, and then moving to the higher count ones. It is easy to see that v7 has to map onto a. Try to work systematically.

    Good luck.

  6. Dec 6, 2015 #5
    I tried that and this is what I got:

    so what is left is c and e,
    I tried once mapping c to 1 and it was wrong (by matrices)
    so I tried it c with 3 and it was wrong as well !!
  7. Dec 6, 2015 #6
    If I was right, the graphs are not isomorphic..
    but how to prove that in a nice way!
  8. Dec 6, 2015 #7


    User Avatar
    Science Advisor
    Homework Helper

    What is wrong with proving that there is no isomorphism, as you apparently did?
  9. Dec 6, 2015 #8
    I mean how to write it in a concise and academic way?
  10. Dec 6, 2015 #9
    Hi Sarah:

    If your purpose is to prove the failure of isomorphism, then you can do that by listing each of the 5 G1 vertices which you successful mapped onto G2 vertices, and for eah mapping write a one sentence explanation of why that mapping is the only mapping possible. Then one sentence each to show that each of the possible remaining 2 mappings are also impossible.

    BTW, I am glad you found out that my guess was wrong.

  11. Dec 6, 2015 #10


    User Avatar

    Staff: Mentor

    You might consider bringing this question to one of the math forums. There may be some denizens there who remember more of their matrix algebra than I do :smile:. (Although it's not entirely disappeared yet!)

    If I recall correctly, for there to be isomorphism the there should exist some transformation matrix T such that ##T~G_1~T^{-1} = G_2##. Does that help?
  12. Dec 7, 2015 #11


    User Avatar
    Science Advisor
    Homework Helper

    Are you sure? I think I have an isomorphism with 3→C and 1→E.
  13. Dec 7, 2015 #12
    I also vaguely recall this relationship. I also vaguely recall for this particular kind of problem, T is a matrix with 1s and 0s only, and there is only one 1 in each row or column. If G1 is set up with the rows and columns organized based on the order of the vertices V1 through V7, and G2 is set up with the rows and columns organized based on the order of the vertices a through g, say A1 through A7, the Tij = 1 if Vi maps to Aj. Does this seem right to you?

  14. Dec 7, 2015 #13


    User Avatar

    Staff: Mentor

    Many little gray cells are producing little grunts of recognition. Presumably T can be decomposed as a sum of elementary row and column operations of the swapping (not scaling) variety.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted