GATE CS 2012 Q38 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the number of distinct cycles of length $4$ (also called $C_4$) in a complete undirected graph $G = K_6$ on $6$ labeled vertices, we can break the process down into two steps:

1. Select the vertices: We need to choose $4$ vertices out of the $6$ available vertices. The number of ways to do this is:$$\binom{6}{4} = \frac{6 \times 5}{2 \times 1} = 15$$
2. Form cycles from the selected vertices: For any set of $4$ chosen vertices, say $\{A, B, C, D\}$, we find the number of unique undirected cycles of length $4$. The number of ways to arrange $k$ vertices in a circle is $(k-1)!$. Since the graph is undirected, a cycle and its reverse are considered identical, so we divide by $2$:$$\text{Number of cycles per 4-vertex set} = \frac{(4-1)!}{2} = \frac{6}{2} = 3$$(Specifically, the three distinct cycles for $\{A, B, C, D\}$ are $A-B-C-D-A$, $A-B-D-C-A$, and $A-C-B-D-A$. )

Thus, the total number of distinct cycles of length $4$ is:

Since $45$ is not present in any of the given options, this question was marked as Marks to All (MTA) by GATE, represented here by X.