Graph Isomorphism Homework: Are 2 Graphs Isomorphic?

[Sarah00]

Homework Statement

Are the 2 graphs isomorphic?

Homework Equations

The Attempt at a Solution

Both have same vertices, edges, set of degrees. But I failed to prove isomorphism by adjacency matrices.

 

[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

 

[Sarah00]

Hi Sarah00:

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

Regards,
Buzz

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

 

[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

 

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

 

[Sarah00]

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

 

[Samy_A]

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

 

[Sarah00]

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

 

[Buzz Bloom]

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

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

 

[gneill]

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?

 

[Samy_A]

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 !

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

 

[Buzz Bloom]

If I recall correctly, for there to be isomorphism the there should exist some transformation matrix T such that
T G₁ T⁻¹= G₂.

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 G₁ is set up with the rows and columns organized based on the order of the vertices V1 through V7, and G₂ is set up with the rows and columns organized based on the order of the vertices a through g, say A1 through A7, the T_ij = 1 if Vi maps to Aj. Does this seem right to you?

Regards,
Buzz

 

[gneill]

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 G₁ is set up with the rows and columns organized based on the order of the vertices V1 through V7, and G₂ is set up with the rows and columns organized based on the order of the vertices a through g, say A1 through A7, the T_ij = 1 if Vi maps to Aj. Does this seem right to you?

Regards,
Buzz

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.