Cayley graph

The Cayley graph is a construction that creates a graph out of a group.

Given a group G and a subset S such that the identity is in S and such that S^-1 = S, the Cayley graph associated with the pair (G,S) is a directed graph which has as vertices the elements of G and for which (g₁, g₂) is an edge if g₁g₂^-1 is in S.

They graph may depend on the choice of the subset S. Cayley Graphs are always vertex-transitive.

The Cayley graph is connected if and only if the set S generates the group G.

When instead of a subset S we take a subgroup H of finite index in G we obtain a graph that is at the basis of coset enumeration or Todd-Coxeter process.