Date: Jan 15, 2013 10:53 AM
Subject: Show Graph G is bipartite with Edges being n! permutations
(before writing I should mention that English isn't my first language. I'm giving my best!)
I want to show, that a Graph G is bipartite, if he's got the following characteristics:
The edges of G are n! Permutations of a_1a_2...a_n while a_1...a_n, b_1...b_n are neighboured, if they only differ by one Transposition (for an example 134562 and 164532).
So, I really do not know where to start. This seems to be not that difficult.
First, I have problems with understanding what is meant by "n! Permutations". A Permutation is defined as a bijective-function, isn't it?
I'm very thankful to any hints :)