I want to show that if $S$ is any subset of $Sym(n)$ such that $S$ contains only transpositions, then the Cayley graph $X=Cay(Sym(n), S)$ is bipartite.
I have figured out that the vertices in $X$ associated with transpositions are pair-wise non-adjacent due to the fact that every permutation is either even or odd and so multiplying two transpositions can't give as a result another transposition. So I think one of my bipartite sets will be the set of transpositions but I am not really sure where to go from here. Any help would be great.