[Math] Number of distinct cycle in complete undirected graph of length $4$

combinatoricsdiscrete mathematicsgraph theory

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

  1. $15$
  2. $30$
  3. $90$
  4. $360$

My attempt :

Number of cycle of lentgh $4$ in undirected graph $= \frac{(n-1)!}{2} =\frac{(4-1)!}{2} = 3$

Number of ways to choose $4$ vertices from the $6$ vertices in undirected graph $^6C_4 = 15$

Therefore, number of distinct cycle in undirected graph is $= 3\times15 = 45$

None of the option matches.

Can you explain in formal way, please?

Edit : The problem was from competitive exam GATE. GATE has marks to all for this question, means either there is no option matches or more than one options are matching.

Best Answer

There are 6 possibilities for picking the first vertex of the 4-cycle,
5 possibilities for then picking the second vertex,
4 possibilities for picking the third vertex,
and 3 possibilities for picking the fourth vertex.

Now we have picked every cycle four times rotated (as a cycle is invariant under rotations) and twice reflected (as we traverse the cycle once clockwise and once counter-clockwise).

Hence the answer is $(6\cdot5\cdot4\cdot3)~/~(4\cdot2)=45$.

Related Question