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.