how to determine if two graphs are not isomorphic

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?

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.

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.

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.

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

Use a computer. "Nauty and Trace" programs gives a computational procedure to solve this problem. This open source package is available from http://pallini.di.uniroma1.it/.

Another helpful link may be http://www.dharwadker.org/tevet/isomorphism/