Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What are some good ways of determining if two reasonably simple looking graphs are not isomorphic? I know that you can check their cycle or some weird property (for certain graphs), but are there some other tricks to do this?

share|improve this question
    
Well, comparing the cardinalities of their sets of vertices is a start (and then their sets of edges...) –  Zev Chonoles Jun 26 '11 at 4:51
    
And others like path-connectedness, and/or number of path-components. A graph isomorphism is basically a relabeling. –  gary Jun 26 '11 at 4:58

4 Answers 4

up vote 4 down vote accepted

As you probably know, graph isomorphism is suspected to be a hard problem (and no efficient algorithms are known that solve the problem). The problem is not known to be NP-Hard either, however.

The easiest ways to prove non-isomorphism quickly are

  • see if vertex-set cardinalities differ
  • see if edge-set cardinalities differ
  • compare degree sequences
  • compare number of connected components (assuming undirected graphs)

There are countless other checks you can make in polynomial time, often via applications of DFS. But none will guarantee that passing the check implies the graphs are isomorphic.

There are randomized algorithms that you can run to test for non-isomorphism: they basically test random parts of the graph hoping to find something askew. Google for "Monte carlo graph isomorphism" if you want more details.

share|improve this answer
2  
One more simple check that can be useful: if two graphs agree on all 4 tests listed above, but one of them has a vertex of degree 3 (say) adjacent to a vertex of degree 4 (say), and the other doesn't, you win. Or if one has a vertex of degree 3, all of whose neighbors have degree 4, while the other doesn't, etc., etc. –  Gerry Myerson Jun 26 '11 at 6:44

Various invariants have already been mentioned. There are also some natural invariants that derive from "linear algebra" properties of the adjacency matrix of the graph, in particular graph eigenvalues and eigenvectors.

These invariants have been much studied. While, unfortunately, they are not powerful enough to establish non-isomorphism in all cases, they are computationally useful, since there is highly efficient software for dealing with large matrices.

share|improve this answer

With practice often one can quickly tell that graphs are not isomorphic. When graphs G and H are isomorphic they have the same chromatic number, if one has an Eulerian or Hamiltonian circuit so does the other, if G is planar so is H, if one is connected so is the other. If one has drawings of the two graphs, our visual systems are so attuned to finding patterns that seeing that the two graphs have some property the don't share often makes it easy to show graphs are not isomorphic.

share|improve this answer
    
Finding chromatic number is NP-hard, which is harder than testing graph isomorphism. Similarly with checking for Hamiltonian circuits. –  ShreevatsaR Jun 26 '11 at 17:41
    
True, but I don't think this question is being asked from the point of view of theoretical computer science. For many small pairs of graphs it may well be easy to see that their chromatic numbers may differ or check their status with regard to having an HC. –  Joseph Malkevitch Jun 26 '11 at 20:40

check vertices-edges correspondence in two different graphs..

for the same degree vertices check the degree of adjacent vertices if the degrees are homogeneous in both graphs then the graph is isomorphic...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.