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.
See also
Explore with Wolfram|Alpha
References
Chase, P. J. "Transposition Graphs." SIAM J. Comput. 2, 128-133, 1973.Clark, D. "Transposition Graphs: An Intuitive Approach to the Parity Theorem for Permutations." Math. Mag. 78, 124-130, 2005.Ganesan, A. "Automorphism Group of the Complete Transposition Graph." 27 Apr 2014. https://arxiv.org/abs/1404.7363.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 9-10, 1990.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Transposition Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TranspositionGraph.html