If L is a list of elements and is an automorphism, L and (L) give equivalent assignment of γ γ elements to the vertices of G. Our task in this stage is to choose exactly one assignment from each equivalence class. Given a fixed ordering of the elements, for example C < O < S, two lists can be compared lexicographically, for example This algorithm is efficient if the automorphism group Aut(G) is small, but that is not always the case. Therefore, we adopt a more complex approach. An automorphism of G is called minor if there are two leaves (vertices of degree 1) x,y with a common neighbour and the automorphism merely swaps x and y; i.e. (x y). The minor subgroup M Aut(G) is the subgroup generated by ≤ all the minor automorphisms. A flower is a maximal set of leaves with the same neighbour. In the left graph of Figure , the flowers are {1,2,3}, {6,10} and {9,11}. The minor subgroup M consists of all automorphisms that preserve the flowers, such as (1 2 3)(9 11). The order of M is . In addition to 3! × 2! × 2! = 24 M, the automorphism group may contain automorphisms that do not preserve the flowers, such as (6 11)(7 8)(9 10). To capture such automorphisms, we colour the graph as in the right side of Figure . Vertices not in flowers are coloured black. Within each flower, vertices are coloured red, blue, green, … in order of vertex number, using a fixed list of colours that does not include black. Now let N be the group of automorphisms that respect the vertex colours. In the example, N has only the identity and (6 9)(7 8) ). An arbitrary automorphism of G can be obtained by first applying an element of N to capture how the flowers are mapped to each other, and then applying an element of M to capture the movement of leaves within each flower. In both steps the choice is unique, so we have a factorization Aut(G) = NM = { | in N, in M }. γδ γ δ (In the language of group theory, M is a normal subgroup and N is a complete set of coset representatives.) In the example, consider (1 2)(6 11)(7 8)(9 10). It swaps the flowers {6,10} and {9,11} so we choose the element of N which does that, namely = (6 9)(7 8) . Then γ we have to arrange the leaves within the flowers with an element of M, namely =(1 2)( for some in N and in M. Note that in both L and L* the δ γ γ δ elements are in nonincreasing order within each flower, as they are maximized with respect to M. Also recall that the automorphisms in N preserve the order of vertex numbers within the flowers, by virtue of the fact that we coloured the vertices in order of vertex number when we computed N. This means that we can take to be identity, and so L* = (L). This proves that L* δ γ = L, since L = max { (L) | in N }. γ γ In order to implement the condition L = max { (L) | in M }, we don't need to compute M γ γ explicitly. Instead, since M is generated by transpositions, it suffices that within each flower the elements are in decreasing order relative to vertex number. Using the ordering of elements that we have chosen, in the example we just need to enforce the inequalities element(1) ≥ element(2) ≥ element(3), element(6) ≥ element and element(9) ≥ element . The program recursively assigns elements to vertices in order of vertex number and enforces these inequalities as they become active rather than at the end.