Proving a (known isomorphic) graph is isomorphic

[in the rye]

Homework Statement

Graph:
Included as an upload or:
http://mgh-images.s3.amazonaws.com/9780073383095/4944-10.3-43IE1.png

Given:
The graph is isomorphic.

Prove that it is indeed isomorphic.

Homework Equations

The Attempt at a Solution

Let the left graph be G(V_g,E_g), and the right graph be H(V_h,E_h)

Since the graph is isomorphic we know:
1) There is a bijective function f from V_g to V_h with the property that a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in V_g.
2) The graphs share the same number of vertices, edges, and degree sequence.

And then from here I'm lost. I know that I have to formulate a bijective function from V_g to V_h which is easy since the cardinality of vertices are the same. The issue I have is being sure that this bijective function has the second property (a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in V_g).

Given that I know the graph is isomorphic, is there any methodical approach to this? I tried messing around with various functions for about 3 hours before I found one that worked. However, there was no method to my madness beyond trial and error.

With simpler graphs, I can kind of tell how the bijective function should be formed because I can visualize a form of the graph that both graphs fit into. For example I can see that a star -- like in graph g -- can unfold into a cycle of 5 vertices (or a pentagon). But as these get more complex I can't. Even breaking the graph into more manageable chunks doesn't seem to help. I'm worried that I won't have enough time to figure these out on a test.

Thanks.

 

[Mark44]

Homework Statement

Graph:
Included as an upload or:
http://mgh-images.s3.amazonaws.com/9780073383095/4944-10.3-43IE1.png

Given:
The graph is isomorphic.

What does this mean? Isomorphism is a comparison of two things. I can't tell what is given here, but the problem seems to be to show that the first graph is isomorphic to the second graph.

Prove that it is indeed isomorphic.

Homework Equations

The Attempt at a Solution

Let the left graph be G(V_g,E_g), and the right graph be H(V_h,E_h)

Since the graph is isomorphic we know:

Since the two graphs are isomorphic ...

1) There is a bijective function f from V_g to V_h with the property that a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in V_g.
2) The graphs share the same number of vertices, edges, and degree sequence.

And then from here I'm lost. I know that I have to formulate a bijective function from V_g to V_h which is easy since the cardinality of vertices are the same. The issue I have is being sure that this bijective function has the second property (a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in V_g).

One technique is to set up an n x n adjacency matrix. If node a is adjacent to node b, put a 1 in the appropriate cell of the matrix, at the row for a and the column for b. Necessarily the (b, a) element of the matrix will be 1, since node a being adjacent to node b means that node b is adjacent to node a.
What does "degree sequence" mean? Does it mean how many edges intersect at a node? If so, you could capture this information in an array of length n, with the first element of the array being how many edges are connected to node a, and so on through the nodes of each graph.

Given that I know the graph is isomorphic, is there any methodical approach to this? I tried messing around with various functions for about 3 hours before I found one that worked. However, there was no method to my madness beyond trial and error.

With simpler graphs, I can kind of tell how the bijective function should be formed because I can visualize a form of the graph that both graphs fit into. For example I can see that a star -- like in graph g -- can unfold into a cycle of 5 vertices (or a pentagon). But as these get more complex I can't. Even breaking the graph into more manageable chunks doesn't seem to help. I'm worried that I won't have enough time to figure these out on a test.

Thanks.

 

[WWGD]

Homework Statement

Graph:
Included as an upload or:
http://mgh-images.s3.amazonaws.com/9780073383095/4944-10.3-43IE1.png

Given:
The graph is isomorphic.

Prove that it is indeed isomorphic.

Homework Equations

The Attempt at a Solution

Let the left graph be G(V_g,E_g), and the right graph be H(V_h,E_h)

Since the graph is isomorphic we know:
1) There is a bijective function f from V_g to V_h with the property that a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in V_g.
2) The graphs share the same number of vertices, edges, and degree sequence.

Why is it difficult? Look at the two degree sequence to help you find the "relabeling" function between the graphs.
And then from here I'm lost. I know that I have to formulate a bijective function from V_g to V_h which is easy since the cardinality of vertices are the same. The issue I have is being sure that this bijective function has the second property (a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in V_g).

Given that I know the graph is isomorphic, is there any methodical approach to this? I tried messing around with various functions for about 3 hours before I found one that worked. However, there was no method to my madness beyond trial and error.

With simpler graphs, I can kind of tell how the bijective function should be formed because I can visualize a form of the graph that both graphs fit into. For example I can see that a star -- like in graph g -- can unfold into a cycle of 5 vertices (or a pentagon). But as these get more complex I can't. Even breaking the graph into more manageable chunks doesn't seem to help. I'm worried that I won't have enough time to figure these out on a test.

Thanks.

Why is it difficult? Use the two degree sequences -- of the respective graphs -- to do the "relabeling" . If g has degree n in G , then find g' with degree n in G' , making sure adjacencies are preserved.

 

[in the rye]

I can't tell what is given here, but the problem seems to be to show that the first graph is isomorphic to the second graph.

This is correct.

Since the two graphs are isomorphic ...
One technique is to set up an n x n adjacency matrix. If node a is adjacent to node b, put a 1 in the appropriate cell of the matrix, at the row for a and the column for b. Necessarily the (b, a) element of the matrix will be 1, since node a being adjacent to node b means that node b is adjacent to node a.

This is how you do the second part of the proof, which is what I'm having trouble with. The bijection is easy for me to spot, but for the adjacency matrix you have to arrange your rows and columns in such a manner that it produces identical matrices for each graph. In this particular case I am having trouble because each vertex has the same number of adjacent vertices. So producing the matrix resulted in trial and error, and I don't think I'd have enough time (on a test) to do this since it took me ~3 hours for this problem. And this particular problem would be be a pretty standard test question for this professor.

What does "degree sequence" mean? Does it mean how many edges intersect at a node? If so, you could capture this information in an array of length n, with the first element of the array being how many edges are connected to node a, and so on through the nodes of each graph.

This is what a degree sequence is. For example if the left graph is graph "G" then we have
deg(u1) = deg(u2) = deg(u3) = ... = deg(u9) = deg(u10) = 3.

Thus the degree sequence of G is 3,3,3,..,3 (ten times).

Why is it difficult? Use the two degree sequences -- of the respective graphs -- to do the "relabeling" . If g has degree n in G , then find g' with degree n in G' , making sure adjacencies are preserved.

I wouldn't say it's difficult. I'd say it's time consuming. As aforementioned it took me 3 hours to get this one.

In this particular case the issue is that each vertex g has a degree of 3 in G. This means your bijective function has 10! (factorial) different possibilities -- which makes preserving the adjacencies difficult to do efficiently (for the sake of a test). In the case of managing the adjacencies, each vertex has 3 possible paths to potentially preserve its structure.

 

[WWGD]

This is correct.
This is how you do the second part of the proof, which is what I'm having trouble with. The bijection is easy for me to spot, but for the adjacency matrix you have to arrange your rows and columns in such a manner that it produces identical matrices for each graph. In this particular case I am having trouble because each vertex has the same number of adjacent vertices. So producing the matrix resulted in trial and error, and I don't think I'd have enough time (on a test) to do this since it took me ~3 hours for this problem. And this particular problem would be be a pretty standard test question for this professor.
This is what a degree sequence is. For example if the left graph is graph "G" then we have
deg(u1) = deg(u2) = deg(u3) = ... = deg(u9) = deg(u10) = 3.

Thus the degree sequence of G is 3,3,3,..,3 (ten times).
I wouldn't say it's difficult. I'd say it's time consuming. As aforementioned it took me 3 hours to get this one.

In this particular case the issue is that each vertex g has a degree of 3 in G. This means your bijective function has 10! (factorial) different possibilities -- which makes preserving the adjacencies difficult to do efficiently (for the sake of a test). In the case of managing the adjacencies, each vertex has 3 possible paths to potentially preserve its structure.

Isn't there a result on graphs with identical degree sequence being isomorphic?

 

[in the rye]

Isn't there a result on graphs with identical degree sequence being isomorphic?

Not that I'm aware of. The reason you check for degree sequence is that in order for it to be an isomorph they must have the same degree sequence. However, having the same degree sequence does not make them isomorphs. For example you could have a connected cyclic graph where n = 8, and another graph of two cycles with n = 4. In this case both graphs would be bipartite, share the same degree sequence, share the same number of vertices, and the same number of edges -- but they are not isomorphs because one is disconnected and the other is connected.

Typically you check the degree sequence, number of edges, whether they are bipartite, the girth, and the number of vertices to check whether or not it's reasonable to assume the graphs are isomorphs. The only way is prove it (as of our current understanding in the class -- and that I'm aware of) is to produce the bijective function.

 

[StoneTemplePython]

Not that I'm aware of. The reason you check for degree sequence is that in order for it to be an isomorph they must have the same degree sequence. However, having the same degree sequence does not make them isomorphs. For example you could have a connected cyclic graph where n = 8, and another graph of two cycles with n = 4. In this case both graphs would be bipartite, share the same degree sequence, share the same number of vertices, and the same number of edges -- but they are not isomorphs because one is disconnected and the other is connected.

Typically you check the degree sequence, number of edges, whether they are bipartite, the girth, and the number of vertices to check whether or not it's reasonable to assume the graphs are isomorphs. The only way is prove it (as of our current understanding in the class -- and that I'm aware of) is to produce the bijective function.

FWIW Graph isopmorphism, from a computational standpoint is a tough problem, generally viewed as being a bit tougher than prime factoring, but not 'quite' NP-Complete.

Sometimes you can reject a claim of graph isomorphism based on spectral properties of the Adjacency Matrices. The first graph in your exercise is a Petersen Graph. This motivates a fun spectral result that "Three Petersens are not Enough" to tile / create a complete graph.

Note: this is available as miniature 13 and 14 of Thirty Three Miniatures, a preliminary version of which is available for free at the author's website, here:

http://kam.mff.cuni.cz/~matousek/la-ams.html and then clicking "preliminary version on-line"

(note: to moderators: see the root page here: http://kam.mff.cuni.cz/~matousek/ )

- - - - -
I'm not sure I have any advice on how to do this problem more quickly by hand, though.