The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Math Topics » alt.math.undergrad

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

Advanced Search

Back to Topic List Back to Topic List  

Posts: 2
Registered: 1/15/13
Show Graph G is bipartite with Edges being n! permutations
Posted: Jan 15, 2013 10:53 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

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