A Graph Question

[Esmerelda]

I got this question in a competitive exam i wrote today...n i was just curious if my answer was right.

The Question is :

Let G be a complete undirected graph on 6 vertices. If vertices of G are labelled, then the number of distinct cycles of length 4 in G is equal to

a) 15 b) 30 c) 90 d) 360

I got the answer as 90...am i right??

[tungnk1993]

The definition of distinct is quite vague but the way I understand is 1-2-3-4-1 and 1-3-2-4-1 is different, meaning order is important.

In order to find distinct cycles of length 4, you need to have 4 distinct vertices and the last vertice is the same as first. Hence, 6P4 = 360

[Esmerelda]

yes but 1-2-3-4-1 is same as 2-3-4-1-2. So shouldnt it be less than 360

[tungnk1993]

If that's the case, then it should be 6C4

[Esmerelda]

No..i dont think so.. it should be more 6C4 and less than 360..
u see the order matters so 1-2-3-4-1 is not the same as 1-3-2-4-1 but since its a cycle 1-2-3-4-1 is same as 2-3-4-1-2, 3-4-1-2-3 and 4-1-2-3-4.

[nupu123]

yah...but according to permuation its value must be 360....plz give me explanation for 90 no. of cycles...

[Esmerelda]

nP4 / 4 =90 since like i said 1-2-3-4-1, 2-3-4-1-2, 3-4-1-2-3 and 4-1-2-3-4 will all be counted in nP4 but it all indicates the same cycle..so i divided it by 4

[tungnk1993]

I still find the definition of 'distinct' quite vague though. Unless a clear definition is given, this question cant be answered easily :)

[Esmerelda]

Well this vague question was given in an Exam written by thousands of engineers across India! It was given in GATE 2012.

[tungnk1993]

Wow, some explanation should be given then :) Or all engineers are smart to know what the question wants :D

[nupu123]

thnx for xplanation....i got it...:-)