# 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. – Yuval Filmus Sep 7 '17 at 10:51
• Have you read the Wikipedia article? – Yuval Filmus 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). – Yuval Filmus 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. – Yuval Filmus 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.