Daniel's answer is imperfect in two respects. First, it defines a perfect hash function for graphs taking values in an arbitrary set, but a "canonical form" usually means more than that in the literature. Second, it is not known to be NP-hard.

Let $\mathcal{G}$ be the set of labelled graphs (usually taken to be finite graphs but that probably doesn't matter). Suppose you can define a function $C:\mathcal{G}\to\mathcal{G}$ satisfying:

• For every $G\in\mathcal{G}$, $C(G)$ is isomorphic to $G$.
• For every isomorphic $G,H\in\mathcal{G}$, $C(G)=C(H)$.

(The last relation is identity not isomorphism.) Then $C(G)$ is called a canonical form of $G$.

One way to define a canonical form (but not the one used in the best algorithms) is to define a total order on labelled graphs then take $C(G)$ to be the least graph in the isomorphism class of $G$.

Daniel's answer is imperfect in two respects. First, it defines a perfect hash function for graphs taking values in an arbitrary set, but a "canonical form" usually means more than that in the literature. Second, it is not known to be NP-hard.

Let $\mathcal{G}$ be the set of labelled graphs (usually taken to be finite graphs but that probably doesn't matter). Suppose you can define a function $C:\mathcal{G}\to\mathcal{G}$ satisfying:

• For every $G\in\mathcal{G}$, $C(G)$ is isomorphic to $G$.
• For every isomorphic $G,H\in\mathcal{G}$, $C(G)=C(H)$.

(The last relation is identity not isomorphism.) Then $C(G)$ is called a canonical form of $G$.

One way to define a canonical form (but not the one used in the best algorithms) is to define a total order on labelled graphs then take $C(G)$ to be the least graph in the isomorphism class of $G$.