Transpositions on a connected graph generate the symmetric group
= Transpositions on a connected graph generate the symmetric group
Associate a <transposition> to each edge of a finite <connected graph>. For a simple path $v_0,\ldots,v_\ell$, let $t_j=(v_{j-1}\ v_j)$. Then $t_1\cdots t_{\ell-1}t_\ell t_{\ell-1}\cdots t_1=(v_0\ v_\ell)$, using rightmost-first composition. Thus edge <transpositions> generate every <transposition>, and hence the full <symmetric group>.