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??
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
yes but 1-2-3-4-1 is same as 2-3-4-1-2. So shouldnt it be less than 360
If that's the case, then it should be 6C4
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.
yah...but according to permuation its value must be 360....plz give me explanation for 90 no. of cycles...
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
I still find the definition of 'distinct' quite vague though. Unless a clear definition is given, this question cant be answered easily :)
Well this vague question was given in an Exam written by thousands of engineers across India! It was given in GATE 2012.
Wow, some explanation should be given then :) Or all engineers are smart to know what the question wants :D
thnx for xplanation....i got it...:-)
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.