A transposition graph 
is a graph whose nodes correspond
to permutations and edges to permutations that differ by exactly
one transposition (Skiena 1990, p. 9, Clark 2005).
The transposition graph 
has vertex count 
, edge count 
(for 
), and is regular of degree 
(Clark 2005). All cycles in transposition graphs are
of even length, making them bipartite.
The transposition graph of a multiset is always Hamiltonian (Chase 1973).
Special cases are summarized in the table below.
