Matching up vertices with the same degree is a good start, but there will still be some (perhaps lots) of trial and error involved. Another good thing to do, once you know some of the correspondences, is to consider unknown matches adjacent to those you already know.
Here is an example which I hope will clarify the above. Please draw the following graphs (I am no good at drawing diagrams online).
- Graph $G$: a pentagon $abcde$, including all five edges $ab,\,bc,\,cd,\,de,\,ea$, and an extra edge $ac$.
- Graph $H$: a square $pqrs$ with edges $pq,\,qr,\,rs,\,sp$, and a vertex $t$ in the middle of the square, with edges $pt$ and $st$.
By considering degrees you could match up vertices as follows:
This is a bijection, but it is not an isomorphism, because $c$ and $d$ are adjacent in $G$ but the corresponding vertices $s$ and $q$ are not adjacent in $H$. So let's take it a bit more slowly.
From degrees, we see that $a$ and $c$ must match $p$ and $s$. Which is which? - perhaps you can see a reason why it doesn't matter, if not then let's just pick one of the options and try it:
Now $b$ is adjacent to both $a$ and $c$, so it must match a vertex adjacent to both $p$ and $s$. The only such vertex is $t$. So now we have
Finally, $d$ is adjacent to $c$ and $e$ is adjacent to $a$, so the only option remaining is
One more point: this does not quite complete the problem since we need to check all adjacencies and non-adjacencies, but we have only checked a few of them. So we could say
- $a$ is adjacent to $b,c,e$ and no others, so $p$ should be adjacent to $t,s,q$ and no others - check - correct.
- and the same for $b,c,d,e$.
This might look like a lot of work - unfortunately, it is a lot of work. However you may be able to redraw the graph $H$ in order to see at a glance that it "looks exactly like" $G$.
Hope this helps.