Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Show Graph G is bipartite with Edges being n! permutations
Replies: 0

 Search Thread: Advanced Search

 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
 Plain Text Reply

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 :)

© The Math Forum at NCTM 1994-2018. All Rights Reserved.