Note that transpositions denoted by a transposition tree of order \(n\)  labeled from 1 to \(n\)  generate \(\mathfrak {S}_n\)  [1]}. However, not every transposition graph having \(n\,(n \ge 2)\)  vertices yields a Cayley graph of \(\mathfrak {S}_n\) . For example, Fig. REF (b) shows a transposition graph having 6 vertices, but it yields a Cayley graph of a group isomorphic to \(C_2 \times C_2 \times C_2\)  instead of \(\mathfrak {S}_6\) , where \(C_2\)  is the cyclic group of order 2.
