mufasa's blog

Complete graph of 6 vertices
By mufasa, 13 years ago, In English

How many unique cycles of length 4 present in a complete Undirected graph of 6 vertices? My answer is 45 and i think its not correct because there are only 4 options 1)15 2)30 3)90 4)360 please share your view

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What's source of the problem? It looks like test question.

→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the answer is 90, if we consider cycles 1 -> 2 -> 3 -> 1 and 1 -> 3 -> 2 -> 1 as different cycles (directed graph).

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    sorry i forgot to mention that graph is undirected.SO obviously 90 reduces to 45

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      It is not so obviously. Forget about directed graph or not, but we can go from x to y, and from y to x for any pair of vertices. The question is: consider we such cycles as one, or they are two different cycles? It is matter for you to go in order Paris, London, Moscow, Berlin, or Berlin, Moscow, London, Paris? Just example. John wants to bring souvenir from Paris to his grandmother in London. And Ivan want to go from Moscow to London. So, for John and Ivan order is matter. Especially if you need to bring a souvenir as soon as possible (perishable food e.g.)

      → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If order and starting vertex don't matter, any set with 4 vertices will uniquely describe a cycle, won't it? The cycle certainly exists, since the graph is complete. So isn't the answer just (6 4) = 6!/(4!2!) = 15 ? [UPD: No, the answer is 90 because of permutations]

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    1 2 3 4, 1 3 4 2, 1 (any permutaion of 3 other vertices (2, 3, 4)). (6, 4) * 3! = 90

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right, thanks. Another way of seeing the math is: Given a subset of 4 vertex, any permutation of its elements results in a different cycle (so the answer would be (6,4) * 4! = 360). However, "cyclic cycles" (like 1 2 3 4 and 2 3 4 1) are the same cycle, and are cleary counted exactly 4 times. So the answer is 360/4 = 90. Thank you very much!

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      you are considering directed graph ..I want solution for Undirected.with any 4 vertices there will be only 3 distinct cycles of length 4 .so answer comes out to be 45

      → Reply