Let G be a group which is finitely generated (see generators and relations for groups for all you ever wanted to know about this terminology). Let S be some finite subset of G which generates G: G = <S>. The *Cayley graph* of G with these generators is the graph Γ=(G,E) whose vertices are the elements of G, with edge set

E = { {u, g*u} : u∈G, g∈S }

That is, connect any 2 vertices of G with an edge

iff they differ by one of the generators.

For example, take G=**Z**^{2}. The set S={(1,0),(0,1)} generates G; its Cayley graph is the square grid which graph theorists usually call just **Z**^{2}. The set {(1,0),(0,1),(1,1),(1,-1)} also generates G; its Cayley graph has additionally "diagonal" edges inside each square of the grid.

If G=**F**_{2} is the free group with 2 generators a,b, we can take S={a,b} which (suprise!) generates G. The Cayley graph is the 4-regular tree. Each element u∈G connects to a*u, b*u, a^{-1}*u, b^{-1}*u, and there can be no loops (multiplying the generators responsible for a loop in the Cayley graph yields 1∈G, and there are no non-trivial relations in the free group).

The Cayley graph describes a geometric structure on the group. It is, of course, dependent on the set of generators chosen. But any 2 Cayley graphs on the same group are quasi-isometric, so the "large-scale" geometry is not *very* different.

Finally, Cayley graphs provide an intuitive description of the group: the path from 1 to a given element exactly describes how to "construct" it by multiplying generators. The graph is highly regular: any neighbourhood N of a vertex u∈G must look *exactly* like a neighbourhood of 1∈G: after all, multiplication on the right by an element of G --- u^{-1} --- preserves edges, so N*u^{-1} is a neighbourhood of 1 which looks exactly like N.