= Cayley graphs of the integers
{c}
{title2=$\operatorname{Cay}_S(\mathbb Z)$}
= Integer Cayley graph
{synonym}
For the additive <infinite cyclic group> $\mathbb Z$, the <generating set of a group> $S=\{-1,1\}$ produces the infinite line: each <integer> $n$ is adjacent to $n-1$ and $n+1$. Adding the moves $\pm2$ gives $T=\{-2,-1,1,2\}$ and additional <edges> skipping one <vertex>. Each skip still costs one step in the <word metric>.
For <integers> $a,b$, these <word metrics> are
$$
d_S(a,b)=|a-b|,\qquad d_T(a,b)=\left\lceil\frac{|a-b|}{2}\right\rceil.
$$
The <absolute value> counts unit moves, and the <ceiling function> counts pairs plus a possible leftover unit. Every $T$-move changes the <integer> by at most two, while moves of size two followed by at most one move of size one attain this bound. For example, the <graph path> $0,1,2,3,4,5$ has five steps for $S$, while $0,2,4,5$ has three for $T$. This calculation gives the concrete comparison
$$
d_T(a,b)\leq d_S(a,b)\leq2d_T(a,b).
$$
\Image[/cayley-integer-generators-and-distances.png]
{title=Two <Cayley graphs of the integers>: unit moves need five steps from zero to five; adding moves of size two needs three}
The picture shows only a finite window of each infinite <Cayley graph>. By contrast, $U=\{-2,2\}$ alone fails to be a <generating set of a group> for $\mathbb Z$: it generates the <subgroup> $2\mathbb Z$. Its move <graph> has two <connected components of a graph>, the <even integers> and the <odd integers>. Within either component the <graph distance> is $|a-b|/2$; between different components no finite <graph path> exists. Adding a shortcut is different from deleting the moves needed for <connectivity (graph theory)>.
Back to article page
