How to show these two graphs are not isomorphic?

In my class they gave me some necessary conditions for two graphs to be isomorphic, these two graphs satisfy all of them but I don't think they're isomorphic:

Degree sequences are equal.

Same amount of vertices/edges.

$G$ is bipartite $\iff H$ is bipartite.

Is there any methodical (quick) way to solve these kind of questions?

Solution 1:

Look at the four vertices of degree $3$ in each graph: in $G$ each of them is adjacent to two of the others, while in $H$ each of them is adjacent to only one of the others. Alternatively, in $G$ they form a $4$-cycle, while in $H$ they do not.

Yet another approach: if you remove them from $G$, what’s left is this graph, with two components.

      *----*  

      *----*

If you remove them from $H$, what’s left is a graph with $4$ vertices and no edges, one with $4$ components.

Solution 2:

In general, this problem is known as graph isomorphism problem and is very hard to solve.

In this special case it can be proven relatively easy. The left graph has a path consisting of 3 distinct vertices of degree 3, but the right graph does not have this property.

Solution 3:

As suggested in other answers, in general to try to show two graphs are NOT isomorphic it suffices to find some invariant conditions, e.g. in terms of counts of vertices of various degrees and counts of their neighbors of various degrees and counts of paths through vertices of different degrees, etc. To show two graphs ARE isomorphic there is basically no known fast method, but you can limit your search for the right isomorphism by using the restrictions outlined above.

In the case of your two graphs, here are examples of how to see they are not isomorphic (similar to other answers). One way is to count the number of vertices of degree 3 that have 2 neighbors also of degree 3. In your first graph the answer is 4, and in the second graph the answer is 0. You can also count how many simple paths there are of length 3 that pass through only degree 3 nodes. In the first graph you can find one, but in the second graph you can't.