How to prove that 2 graphs are not isomorphic?

[AdrianZ]

Hi

Well, I know that in some few special cases It is easy to prove that 2 graphs can not be isomorphic. for example if they gave us two graphs that one of them were bipartite and the other were not, we can state that if the 2 graphs were isomorphic, then they would've had same mathematical properties. but is there anyway, in general, that can tell us whether 2 graphs are isomorphic or not? and if yes, how can we find a bijection between these two? in simple cases it might be not so hard, but when the number of vertices and edges increase this will certainly become very difficult.

I'm also looking for a way to prove Havel-Hakimi theorem. I'm new to Graph theory, so please don't introduce me very advanced stuff that I don't understand anything from them. lol another question, It's really hard for me to solve all the questions that my book wants me to solve them for practice. is there something wrong with me or It's a common phenomena when someone is new to graph theory? lol

Thanks

 

[micromass]

Well, I guess that there are many people here who know more about graph theory, but I think that I can provide a decent answer to your question.

Proving that two objects (graphs, groups, vector spaces,...) are isomorphic is actually quite a hard problem. So I wouldn't be surprised that there is no general algorithm for showing that two graphs are isomorphic. In general, there are two cases:
- the objects are isomorphic: then the only thing you can do is to find an explicit isomorphism. You may be able to use fancy theorems, but in the end, you'll need to provide an isomorphism.
- the objects are not isomorphic: this is the hardest part. Showing that two objects are not isomorphic can be quite tricky. The only way to do something like this is to find a property that one object has, and that the other does not. For example, show that one graph is bipartite and the other is not. Or show that there is an Euler/Hamilton circuit that the other does not have.

But knowing in which case that you are is really difficult. In fact, some of the most important unsolved problems in mathematics are of this type. I think of the Pointcarre conjecture which asks when an object is "isomorphic" to a sphere. Or the Suslin hypothesis, which asks when an object is "isomorphic" to the real line.

It's quite possible that somebody will post a cool theorem in this thread which immediately allows one to see when two graphs are isomorphic, but I dount such a theorem exist. In fact, the only way one can answer the question is, I think, finding an explicit isomorphism or finding a property that one space shares and the other one does not...

 

[AdrianZ]

Thank you.

any ideas about how to prove Havel-Hakimi theorem?

 

[disregardthat]

Write up the graphs in matrix form. Order the nodes by integers 1,2,...,n, and let the row i and column i correspond to the node i, and let the (i,j)'th entry be 1 if there is an edge between the i'th and j'th node, and 0 if there is not.

Two graphs are isomorphic if and only if the two corresponding matrices can be transformed into each other by permutation matrices.

I will try to think of an algorithm for this. Of course you could try every permutation matrix, but this might be tedious for large graphs.

EDIT:

Ok, this is how you do it for connected graphs. A matrix for a connected graph is invertible (i think!), so if your matrices are A and B, all you have to do is to check whether A^(-1)B is a permutation matrix. That is if and only if by row switching you can get the identity matrix. Just check that each row and column consist of one entry 1, and the rest are 0. If your graphs are not connected, do this for each connected component. Still, if there are many components you will have to check each component to another, which again may be tedious.

 

[Robert1986]

In general, this problem isn't easy. It has a worst-case exponential run time. It is an NP-Indeterminate problem, and, in fact, a new complexity class was created (GI, I think) to study graph isomorphisms. However, there are many special cases that are solvable in polynomial time.