[1][2] Conversely, every complete invariant of graphs may be used to construct a canonical form.
[5] While the existence of (deterministic) polynomial algorithms for graph isomorphism is still an open problem in computational complexity theory, in 1977 László Babai reported that with probability at least 1 − exp(−O(n)), a simple vertex classification algorithm produces a canonical labeling of a graph chosen uniformly at random from the set of all n-vertex graphs after only two refinement steps.
Small modifications and an added depth-first search step produce canonical labeling of such uniformly-chosen random graphs in linear expected time.
This result sheds some light on the fact why many reported graph isomorphism algorithms behave well in practice.
A commonly known canonical form is the lexicographically smallest graph within the isomorphism class, which is the graph of the class with lexicographically smallest adjacency matrix considered as a linear string.
[8] For trees, a concise polynomial canonization algorithm requiring O(n) space is presented by Read (1972).
If there are two vertices remaining, concatenate their labels in lexicographic order.