I would avoid guessing in cases where it seems like a vertex in one graph might match up with multiple vertices in another graph. Instead, start from places where the bijection is unique, and extend it from there.
In this example, $C$ is the only vertex of graph (a) with degree $4$, and $D$ is the only vertex of graph (c) with degree $4$, so a graph isomorphism $\phi$ from one to the other must have $\phi(C) = D$.
Then we look at $C$'s neighbors in (a) and try to match them up with $D$'s neighbors in (c). There's two neighbors of degree $2$, and two neighbors of degree $3$, so there's four ways to match them up:
- Either $\phi(B) = E, \phi(D) = G$ or $\phi(B) = G, \phi(D) = E$.
- Either $\phi(F) = A, \phi(G) = B$ or $\phi(F) = B, \phi(G) = A$.
In this case, it doesn't matter which way we choose: the set of $B$'s neighbors in (a) is the same as the set of $D$'s neighbors in (a), so they're interchangeable, and the same for $F$ and $G$.
Then we look at the remaining vertices. Say we chose $\phi(B) = E$. Then we must have $\phi(A) = F$, because we must choose a neighbor of $E$ in (c). Similarly, we get $\phi(E) = C$, completing the isomorphism.
Now we check that all the edges get mapped to edges, and because we never made guessing steps, either things work out or there is no isomorphism.
I'm not saying you can always avoid guessing, but you can minimize it. If there were no vertices with unique degree, you could look for unique substructures instead: for example, both graphs have only two triangles (triples of vertices all connected to each other), so those have to be matched up.
Sometimes you just get a place where the graphs are highly symmetric, and can't avoid guessing. But that's where actual graph isomorphism algorithms get stuck, too.
