Here is an amusing thing I hadn’t properly realized until recently: depending on the definition, the Cayley graph of $latex \mathbf{Z}/2\mathbf{Z}$ with respect to the symmetric generating set $latex \{1\}$ can be either a single arrow joining two vertices
or a cycle of length 2:
The first case occurs when one is not careful, taking as edge set of $latex \mathcal{C}(G,S)$ the set
$latex E=\{\{g,gs\}\,\mid\, g\in G\,\ s\in S\}$
(as was probably to be expected, my notes on expander graphs use this naïve definition…)
The second case occurs (at least) when one is Serre, as can be checked from the definition in “Trees”, and the resulting illustration:
(in a French printing of that book which I have seen, Serre specifically warns that the two edges are not the same).
The questions are, which is the “right” definition, if any? and should this matter? To a large extent, the answer to the second is (fortunately) “not really”, though the same issue arises for any Cayley graph where some generator is an involution.
Either choice has some potentially annoying features:
(1) The canonical choice (Serre’s) has the effect that any Cayley graph of a group with respect to a generating set containing an involution has multiple edges; for instance, the following picture taken from P. de la Harpe’s “Topics in geometric group theory”
is supposed to be the Cayley graph of $latex \mathrm{PSL}_2(\mathbf{Z})$ with respect to a generating set for which it is a free product of cyclic groups of order 2 and 3 (generated by $latex b$ and $latex a$, respectively), but is wrong with the canonical definition. (To be fair, de la Harpe mentions the issue, and says that he uses the naïve definition because that is not a problem for his purposes.)
(2) In the canonical choice, the formula
$latex M\varphi(x)=\frac{1}{|S|}\sum_{s\in S}{\varphi(xs)}$
for the Markov averaging operator is usually wrong. (E.g., for the example of $latex \mathrm{PSL}_2(\mathbf{Z})$ above.) In particular, the spectrum of the Laplace operator is not the same depending on which definition is used…
(3) Similarly, the Cayley graph $latex \mathcal{C}(G,S)$ is not always $latex |S|$-regular.
(4) However, in the non-canonical choice, it follows that a Cayley graph of a finite group may have infinite girth (being a tree, as in the example of $latex \mathbf{Z}/2\mathbf{Z}$…) Correspondingly, the interpretation of the girth of a Cayley graph as the smallest length of a non-trivial relation in the generators may fail…
At the moment, as I said, I use the naïve definition in my notes (most books I’ve seen which bother to define the Cayley graph in a formally precise way seem to do the same, though the definition is often sufficiently fuzzy that it doesn’t take much effort to accommodate both possibilities…) But I claim somewhere that the Cayley graph of $latex \mathbf{Z}/m\mathbf{Z}$ (with respect to $latex \{\pm 1\}$) is a cycle of length $latex m$, which is then wrong for $latex m=2$.
I haven’t quite decided how I will change the text, since I tend to like the formula for the Markov averaging operator. Maybe, like de la Harpe, I will just mention both possibilities and use the naïve one. Certainly, as far as expander graphs are concerned, this has no consequence on the property of being or not an expander for a sequence of Cayley graphs (of bounded valency).
