# Canonical graph

**URL:** <https://community.wolfram.com/t/canonical-graph/5426>\
**Category:** Questions\
**Tags:** graphs-and-networks\
**Created:** [April 14, 2015, 8:08pm UTC](https://community.wolfram.com/t/canonical-graph/5426 "2015-04-14T20:08:27Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![stuartmarshall](https://avatars.discourse-cdn.com/v4/letter/s/53a042/32.png) [@stuartmarshall](https://community.wolfram.com/u/stuartmarshall)\
**Post date:** [April 14, 2015, 8:08pm UTC](https://community.wolfram.com/t/canonical-graph/5426/1 "2015-04-14T20:08:27Z")

</div>

Hello

I’m wanting to find out what the definition of canonical graph labelling is for the canonicalgraph function in mathematica. Any ideas where I can get that information? All I can see in the description is that it puts the graph in a canonical form, but no indication on what that form is e.g. Maximising or minimising sequences from the adjacency matrix etc.

Cheers

---

<div class="post-metadata">

**Author:** ![sblinder](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/sblinder/32/17861_2.png) [@sblinder](https://community.wolfram.com/u/sblinder)\
**Post date:** [April 16, 2015, 7:27pm UTC](https://community.wolfram.com/t/canonical-graph/5426/2 "2015-04-16T19:27:06Z")

</div>

Graph canonization is a NP-hard computational problem. A discussion of canonical graphs is given, for example, in

[http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf](http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf)

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/szhorvat/32/3531_2.png) [@szhorvat](https://community.wolfram.com/u/szhorvat)\
**Post date:** [February 4, 2018, 10:35am UTC](https://community.wolfram.com/t/canonical-graph/5426/3 "2018-02-04T10:35:32Z")

</div>

For the intended application, it does not matter. What is important is that `g1` and `g2` are isomorphic if and only if `CanonicalGraph[g1] === CanonicalGraph[g2]`.

There are many different ways to define (and compute) a canonical form with this property. All of them are complicated. For example, the [Bliss](http://www.tcs.hut.fi/Software/bliss/) library (which you can access in Mathematica through [IGraph/M](http://szhorvat.net/mathematica/IGraphM)) provides multiple such forms.