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?
On
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.
On
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.
On
Yet another difference: In G, you can remove a pair of adjacent vertices to disconnect the graph. The graph H does not have this property, though.
Remember the old joke about, "How do I get to Carnegie Hall?" "Practice, practice, practice!" ? The same thing applies here. You look for a property that one graph has that the other one doesn't, and the more properties you know, and the more practice you get, the easier it becomes.
On
$G$ is Hamiltonian (has a cycle using every vertex once) and $H$ is not.
To see the second point, $H$ has several vertices of degree $2$. Any Hamilton cycle must use all the edges on these vertices. But those edges form a pair of $4$-cycles, and cannot be part of a cycle on all the vertices.
On
A vertex cover of a graph is a subset $C$ of the vertices such that at least one vertex of every edge is in $C$. A vertex cover $C$ is minimal if no proper subset of $C$ is a vertex cover. If two graphs are isomorphic then there must be a size-preserving bijection between their sets of minimal vertex covers.
To see that the given graphs are not isomorphic let's label the vertices of the graphs like so:
$G$ with a vertex labeling" />
$H$ with a vertex labeling" />
There are precisely two minimal vertex covers of $G$ of size four: $\{a,d,e,h\}$ and $\{b,c,f,g\}$. But there are three such covers of $H$: $\{a,d,e,f\}, \{b,c,e,f\}, \{b,c,g,h\}$. So the two graphs can't be isomorphic.
For larger examples computing minimal vertex covers by hand is arduous. Fortunately there is open source software available for quickly compute minimal vertex covers. For example one can use the Macaulay2 package EdgeIdeals to compute all of the minimal vertex covers of both graphs as follows.
i1 : loadPackage "EdgeIdeals";
i2 : S = ZZ/2[a..h]; -- a polynomial ring in 8 variables, one for each vertex
i3 : G = graph (S, {{a, b}, {a, c}, {b, d}, {c, d}, {c, e}, {d, f}, {e, f}, {e, g}, {f, h}, {g, h}});
i4 : H = graph (S, {{a, b}, {a, c}, {b, d}, {b, e}, {c, d}, {c, f}, {e, g}, {e, h}, {f, g}, {f, h}});
i5 : I = coverIdeal G
o5 = monomialIdeal (bcfg, acdfg, adefg, adeh, bcdeh, bcefh)
o5 : MonomialIdeal of S
i6 : J = coverIdeal H
o6 = monomialIdeal (bcef, adef, bcgh, acdegh, abdfgh)
o6 : MonomialIdeal of S
We see from the output in line o5 that $G$ has a total of 6 minimal covers: two of size four and four of size five. On the other hand line o6 shows that $H$ only has five: three of size four and two of size six.
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.