# Canonical form for a graph

I am trying to find a description for canonical form (labelling) for a graph. Specifically, how do we arrive at canonical form for a given graph?

• Nobody knows how to do this efficiently in general. Sep 7 '17 at 10:51
• Have you read the Wikipedia article? Sep 7 '17 at 11:02
• Yes, it mentions lexicographically smallest graph. But it doesn't define exactly the term "lexicographically small".
– mach
Sep 7 '17 at 11:34
• You go over all different orders for vertices, and choose the one which results in the lexicographically smallest representation. Note that there might be other ways to canonicalize graphs (in which the canonical form is not the lexicographically smallest representation). Sep 7 '17 at 11:38
• I just described such an algorithm. Of course, it's not very efficient. As I said in my first comment, nobody knows how to efficiently canonicalize graphs. If we could do it, we would have solved the graph isomorphism problem. Sep 7 '17 at 11:52

Graph canonization is a a procedure that takes a graph $G$ and returns an isomorphic graph $C(G)$, we the promise that $C(G) = C(H)$ iff $G$ and $H$ are isomorphic. We call $C$ a canonical form.
One possible canonical form is the lexicographically smallest adjacency matrix. Given an ordering of the vertices, we can serialize the adjacency matrix as a binary string. Given a graph $G$, we choose the ordering leading to the lexicographically smallest such string, and then order the graph accordingly to form $C(G)$. It is not hard to check that this is a canonical form.