# Selecting the right partition in NAUTY

Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and attempt to further split the partition on more cells. What I found is that depending on the order of which you select cells during refinement, you can get different equitable partitions (at least up to the permutation of cells in the equitable partition). I guess this corresponds to the quote from Practical Graph Isomorphism II:

It is well known that for every colouring π there is a coarsest equitable colouring π' such that π' < π, and that π' is unique up to the order of its cells.

An example of this would be Example 7.7 (page 257), where selecting {1,3,7} instead of {2,4,5,6} will result in a permuted equitable partition

And more importantly these 2 equitable partitions can give 2 different certificates, so it is important to select the right order on the cells to get minimal among possible equitable partitions.

So my question is how does nauty ensure that during refinement it will find the “right” equitable partition and not lose the equitable partition that would potentially lead to the minimal certificate? In order words, among all (a) coarsest partitions how does it make sure to select the coarsest partition (because it selects just one equitable partition)?