Maths - Cayley Graph

The Cayley graph is a graph where each node represents an element of the group. We then choose one or more elements as generators and these are represented by arrows. We only need to choose enough generators so that the graph is connected (no nodes are isolated).

There is some freedom of choice in selecting the generators for a given group, this means that equivalent (isomorphic) groups may look quite different if we choose different generators.

Lets take a simple example to start with: C3. The group elements are e,r and r² so we can draw these as nodes. We then have to choose our generators, the identity element 'e' would just produce arrows from each element back to itself, so we never use the identity element as a generator as it does not help connect up the nodes. We can try 'r' as a possible generator, this has arrows as follows:

This fully connects the nodes so we don't have to choose any other generators as this connects all the nodes as required.

We could have chosen r² as our generator, this would have been just as good, in this case the arrows would have gone in the opposite direction.

From the Cayley graph we can derive the full multiplication table as follows:

 e r r² r r² e r² e r

We can easily generate the columns for the generators as each entry is directly represented by an arrow. The other columns can be derived from these, in this case r² can be derived by applying r twice.