Date: Jan 15, 2013 10:53 AM
Author: M.K.
Subject: Show Graph G is bipartite with Edges being n! permutations

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 bijective-function, isn't it?

I'm very thankful to any hints :)