Cayley Graph - Characterization

Characterization

The group acts on itself by the left multiplication (see Cayley's theorem). This action may be viewed as the action of on its Cayley graph. Explicitly, an element maps a vertex to the vertex . The set of edges of the Cayley graph is preserved by this action: the edge is transformed into the edge . The left multiplication action of any group on itself is simply transitive, in particular, the Cayley graph is vertex transitive. This leads to the following characterization of Cayley graphs:

Sabidussi Theorem: A graph is a Cayley graph of a group if and only if it admits a simply transitive action of by graph automorphisms (i.e. preserving the set of edges).

To recover the group and the generating set from the Cayley graph, select a vertex and label it by the identity element of the group. Then label each vertex of by the unique element of that transforms into The set of generators of that yields as the Cayley graph is the set of labels of the vertices adjacent to the selected vertex. The generating set is finite (this is a common assumption for Cayley graphs) if and only if the graph is locally finite (i.e. each vertex is adjacent to finitely many edges).