Post #3
(isolation #0)
» Thu Apr 19, 2018 6:28 am
Start with a specific permutation. If all the characters in the string of length n are distinct, there are (n choose 2) possible inversions to perform, and therefore (n choose 2) neighbours to the corresponding vertex.
On the other hand, if any two characters in the permutation are the same, inverting the substring starting and ending with these characters is the same as inverting the substring between these two characters. Therefore, each pair of copies of characters reduces the number of distinct permutations that can be created by inversion (and therefore the number of neighbouring vertices) by 1.
Note that there are two degenerate cases: If two copies of the same character are consecutive or have a third arbitrary character between them, then the corresponding substring between these two copies is too short to be inverted; once again such an inversion can be ignored when counting the degree of a vertex.
Since every vertex corresponds to a permutation of the same collection of characters, the number of pairs of copies of characters, k, is the same for every vertex. Then, the degree of every vertex is (n choose 2) - k, and the graph is regular.
I'm sleepy, so I hope I didn't mess the reasoning up. I also can't think of any interesting problems right now, so someone else can ask something, instead.
You don't have ambiguity; you have options.