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.