Graph Isomorphism

1. Dec 6, 2015

Sarah00

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. Dec 6, 2015

Buzz Bloom

Hi Sarah00:

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

Regards,
Buzz

3. Dec 6, 2015

Sarah00

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??

4. Dec 6, 2015

Buzz Bloom

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.

Regards,
Buzz

5. Dec 6, 2015

Sarah00

I tried that and this is what I got:
a=7
b=2
f=5
d=4
g=6

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 !!

6. Dec 6, 2015

Sarah00

If I was right, the graphs are not isomorphic..
but how to prove that in a nice way!

7. Dec 6, 2015

Samy_A

What is wrong with proving that there is no isomorphism, as you apparently did?

8. Dec 6, 2015

Sarah00

I mean how to write it in a concise and academic way?

9. Dec 6, 2015

Buzz Bloom

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.

Regards,
Buzz

10. Dec 6, 2015

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 . (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?

11. Dec 7, 2015

Samy_A

Are you sure? I think I have an isomorphism with 3→C and 1→E.

12. Dec 7, 2015

Buzz Bloom

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?

Regards,
Buzz

13. Dec 7, 2015

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.