1
$\begingroup$

A graph is made whose vertices correspond to all the different permutations of ${1,2,3,4,5}$. Two vertices are adjacent iff they agree on exactly one place (i.e. exactly one place of the 5 places of permutations is same and the rest all has to be different) of their permutations. What can we say about the graph?

1) How many vertices and edges are there in the graph?

2) Is the graph planar, bipartite or/and regular?

I have worked for the set ${1,2,3}$. I got 6 vertices and 9 edges which is bipartite, regular but not planar.

I tried for the permutations of ${1,2,3,4}$ and I get degree of each vertex as 8. and I am stuck here. How to hit for the permutations of 5 numbers?

$\endgroup$
  • $\begingroup$ Hint: Take an example of any one particular permutation and work out how many vertices it will be adjacent to. $\endgroup$ – Shahab Feb 16 '14 at 12:01
  • $\begingroup$ I worked for 4 numbers and I got it 8 different adjacent vertices. But is there and proper method to work out this in general for large sets? Except trial and error? it will be helpful for me.. $\endgroup$ – Nimit Feb 16 '14 at 12:06
2
$\begingroup$

There there are $5!$ possible permutations or equivalently $5!$ ways to write the numbers $1,\cdots, 5$ in any order. This is because for the first place there are $5$ options, and once that is decided for the second there are $4$ options and so on. So there are a total of $5\times 4\times 3\times 2\times 1=5!=120$ possible ways. This means that the graph has $5!$ vertices.

Now take any fixed vertex $abcde$. Let us consider its those adjacent vertices which are of the form $a****$. Clearly $****$ is some derangement of $bcde$. There are $9$ such derangements possible as per oeis and so there are $9$ such vertices. Since the argument could be identical for vertices where any other vertex than $a$ is fixed so this means that there are $9\times 5=45$ vertices adjacent to $abcde$. So the graph is $45$-regular and so has $2700$ edges. Further as $abcde-acdeb-badce$ is a triangle so the graph is not bipartite. For a planar graph it is necessary that the number of edges is at most $3n-6$ where $n$ is the number of vertices. This criteria is not fulfilled as $2700\not\le 3\times 120-6$. So the graph is not planar.

This argument may be generalized.

$\endgroup$
  • $\begingroup$ I got stuck in 'derangement' only. Very well explained. Thanks a lot. $\endgroup$ – Nimit Feb 16 '14 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.