I am trying to understand the nauty algorithm. I do not understand why the search tree is needed. As far as I understood after refining based on the neighbour information propagation a search tree is started, in which the vertices are artifically destinguished.
The search tree's leaf nodes represent canonical permutations (as far as I understood). If so why do we search for more than one leaf? Aren't canonical forms of isomorphic graphs defined as identical, with C(G)=C(H), for H isomorphic to G, and so one canonical representation per Graph should be enough to check for isomorphism?
I used these articles https://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf https://pallini.di.uniroma1.it/Introduction.html as a guide (mainly the first).
So nAUTy - at a very high level - finds all the automorphisms of a graph and then picks one as the canonical one. The leaves of the tree are the automorphisms, but only one leaf is canonical.
One way to think about this is to consider a much simpler (and less efficient!) algorithm. Just permute the labels on the graph in all possible ways (n factorial) and pick the one that is both an automorphism and maximises the upper-half triangle of the adjacency matrix.
That is, make a 'certificate' for a graph based on some procedure (such as maximising the matrix) which can then be compared for equality. In nAUTy, this certificate is the canonical permutation (C) applied to the graph. For example, if you relabel the vertices of the graph according to C and then write out the edges as a string, you get such a certificate.
So in summary, no you have to find the 'right' leaf of the tree for each of G and H, so that you can compare the certificates for each for equality.