Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


M.K.
Posts:
2
Registered:
1/15/13


Show Graph G is bipartite with Edges being n! permutations
Posted:
Jan 15, 2013 10:53 AM


Greetings! (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 bijectivefunction, isn't it?
I'm very thankful to any hints :)



