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.
is a graph whose nodes correspond
to permutations and edges to permutations that differ by exactly
one transposition (Skiena 1990, p. 9, Clark 2005).
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.
