Cayley graph

Let $G$ be a group with a finite generating set $S\subset G$, such that:

• $e\notin S$ (the identity is excluded),
• $S=S^{-1}$, meaning that for every element $s\in S$, its inverse $s^{-1}$ is also in $S$.
  The Cayley graph $\mathrm{Cay}(G,S)$ is a graph defined as follows:
• Vertices: each element $g\in G$,
• Edges: for each $g\in G$ and $s\in S$, draw an edge between $g$ and $gs$.
  Because $S=S^{-1}$, this construction yields an undirected graph: if there is an edge from $g$ to $gs$, there is also an edge from $gs$ to $g$, since $s^{-1}\in S$.

Examples. Cayley graph of the group of symmetries of a square (i.e., the dihedral group $D_4$) with generators the rotation $a$ and the horizontal reflection $b$.

Cayley graph of $D_4$ with generators the horizontal reflection $b$ and the diagonal reflection $c$:

Cayley graph of the free group with two generators:

Geometric Viewpoint:

The Cayley graph serves as a combinatorial, geometric representation of the group $G$.
When $G$ is a discrete subgroup (such as a lattice) of a Lie group $\mathcal{G}$, the Cayley graph of $G$ can be interpreted as a discretized version of the smooth manifold structure of $\mathcal{G}$. For example:

• The Cayley graph of ${\mathbb{Z}}^n$ (with standard generators) is an infinite grid, which discretely models the geometry of Euclidean space ${\mathbb{R}}^n$.
• In the large-scale (or "coarse") sense, this graph reflects the geometry of the continuous Lie group it approximates. See Discrete Differential Geometry.