Fig. REF  shows the bubble sort graph \(\text{BS}_4\)  of the transposition tree \(T=(<4>, S_1)\) . Since adjacent transpositions \((1\,2), (2\,3)\) , and \((3\,4)\)  generate \(\mathfrak {S}_4\) , \(\text{BS}_4\)  has \(|\mathfrak {S}_4|=24\)  vertices, each of which has degree 3. To find a path from permutation \(p_1\)  to permutation \(p_2\)  in \(\text{BS}_4\)  is obtained by using the bubble sort algorithm [1]}. For example, let vertex \(v_1\)  be \(2\,1\,3\,4\)  and vertex \(v_2\)  be \(3\,1\,4\,2\)  in \(\text{BS}_4\) . Then, to find path \(p\)  from \(v_1=2\,1\,3\,4\)  to \(v_2=3\,1\,4\,2\)  is equivalent to find path \(p\)  from
\(v_2^{-1}v_1=4\,2\,1\,3\)  to permutation \(I\) : \(4\,2\,1\,3 \xrightarrow{}\)\( 2\,4\,1\,3 \xrightarrow{} \)\(2\,1\,4\,3 \xrightarrow{} \)\(2\,1\,3\,4 \xrightarrow{} \)\(1\,2\,3\,4\) ,
where the label of each arrow denotes an edge in \(\text{BS}_4\) . Thus, we have \(p=(1\,2)(2\,3)(3\,4)(1\,2)\) .
<FIGURE>