Cayley graph

Cayley graph also know as Cayley colour graph, Cayley diagram, group diagram, or colour group  is a graph that encodes the abstract structure of a group

Definition Suppose that G is a group and S is a generating set. The Caylet graph \Gamma=\Gamma(G,S) is a colored directed graph constructed as follows

  • Each element g of G is assigned a vertex: the vertex set V(\Gamma) of \Gamma is identified with G.
  • Each generator s of S is assigned a color c_s.
  • For any g\in G,s\in S, the vertices corresponding to the elements g and gs by a directed edge of colour c_s. Thus the edge set E(\Gamma) consists of pairs of the form (g,gs), with s\in S providing the color.

In geometric group theory, the set S is usually assumed to be finite, symmetric and not containing the identity element of the group. In this case, the uncolored Cayley graph is an ordinary graph; its edges are not oriented and it does not contain loops (single-element cycles).