Triangle-Free Cayley Graph

In this note I elaborate the proof of a claim regarding Cayley graphs of symmetric groups with transpositions as generators that I found in the book Algebraic Graph Theory by Chris Godsil and Gordon Royle. This claim appears as commentary in Section 3.10 about Transpositions. Here I present it in the form of a theorem along with a complete proof.

Theorem. If \( \mathcal{T} \) is a set of transpositions, then the Cayley graph \( X(\operatorname{Sym}(n), \mathcal{T}) \) has no triangles.

Proof. Suppose the vertices \( a, b, c \in \operatorname{Sym}(n) \) form a triangle in the Cayley graph \( X(\operatorname{Sym}(n), \mathcal{T}). \) Since multiplication by \( a^{-1} \) is an automorphism of the Cayley graph (by the proof of Theorem 3.1.2 that comes earlier), the vertices \( e, ba^{-1}, ca^{-1} \) form a triangle too. Let us label them as \( e, b', c' \) respectively.

Now by the definition of a Cayley graph, for any two vertices \( a, b \in \operatorname{Sym}(n), \) we have \begin{align*} a \sim b & \iff ba^{-1} \in \mathcal{T} \\ & \iff ba^{-1} = g \\ & \iff b = ga \end{align*} for some \( g \in \mathcal{T}. \) Therefore \begin{align*} e \sim b' & \iff b' = ge = g, \\ e \sim c' & \iff c' = he = h, \\ b' \sim c' & \iff c' = lb' \end{align*} for some \( g, h, l \in \mathcal{T}. \) Note that the last equality gives \[ l =c'b'^{-1} = hg^{-1} = hg \in \mathcal{T} \] Therefore \( g, h, hg \in \mathcal{T}. \) However, this is impossible since the product of two transpositions is \( e, \) a \( 3 \)-cycle or a product of two disjoint transpositions. For example, \( (12)(12) = e, \) \( (12)(13) = (123) \) and \( (12)(24) = (12)(24). \) Therefore \( hg \) cannot be a transposition, i.e. \( hg \notin \mathcal{T}. \) This is a contradiction. Therefore the vertices \( a, b, c \) cannot form a triangle. We conclude that the Cayley graph \( X(\operatorname{Sym}(n), \mathcal{T}) \) has no triangles.