Let G be a complete undirected graph on 6 vertices. If vertices of G are…

Concept: To count how many copies of a k-vertex cycle sit inside a complete graph on labeled vertices, first choose which vertices participate, then count the distinct cyclic arrangements those chosen vertices can form, collapsing arrangements that trace the same cycle (rotations of the starting point and the two directions of travel all give the same undirected cycle).

Applying it here:

1. A 4-cycle needs exactly 4 of the 6 vertices; the number of ways to choose which 4 is C(6,4) = 15.

2. For one chosen set of 4 labeled vertices, fix one vertex and arrange the remaining 3 around it: that gives (4 - 1)! = 6 orderings. Each undirected cycle is produced twice this way (once per direction of travel), so divide by 2: 6 / 2 = 3 distinct undirected cycles per set.

3. Multiply the vertex-selection count by the per-set cycle count: 15 x 3 = 45.

Cross-check: List ordered sequences instead: arranging 4 distinct vertices out of 6 in order gives P(6,4) = 6 x 5 x 4 x 3 = 360 sequences. Every undirected cycle appears 4 x 2 = 8 times in this ordered list (4 possible starting vertices, 2 directions), so 360 / 8 = 45, the same total.

Answer: 45 distinct 4-cycles.