I am trying to figure out how Luks' graph isomorphism algorithm works, I understand the clear answer given by Misha Lavrov about trivalent graph isomorphism, it basically says:
Construct graph $Z$ by joining graphs $X, Y$ in a specific way,
Find the automorphism group of $Z$,
If there is isomorphism between graph $X$ and graph $Y$, then, there will be an automorphism, say $\pi$, that sends vertices from $X$ to $Y$, in that case $\pi$ is the isomorphism, i.e. $X^{\pi}=Y$. If there is no such $\pi$, then graphs are not isomorphic.
But I got confused when I read the thesis of Paolo Codenotti (page 33 to 35), In the subsection 2.5.2 "Divide and conquer", the author describes the process of $\rm ISO(G; X, Y )$ where $G \leq \rm Sym (X)$.
But I don't understand how $G$ is chosen, there is no clear description on the document. Say,
$\rm ISO(G; X, Y ) = \emptyset$ does that mean there is no isomorphism between $X, Y$?
That can't be because, it could be the case that there exists $H$ such that $G < H \leq \rm Sym (X)$ and $\rm ISO(H; X, Y ) \neq \emptyset$, right?
The question is, how we choose a group $G$ and be sure that if $\rm ISO(G; X, Y ) = \emptyset$ then there is no isomorphism between $X, Y$?