Let G be a complete undirected graph of 6 vertices. If vertices of G a...
There can be total 6C4 ways to pick 4 vertices from 6. The value of 6C4 is 15.
Note that the given graph is complete, so any 4 vertices can form a cycle.
There can be 6 different cycle with 4 vertices. For example, consider 4 vertices as a, b, c and d.
Cycles should be like this:
(a, b, c, d, a)
(a, b, d, c, a)
(a, c, b, d, a)
(a, c, d, b, a)
(a, d, b, c, a)
(a, d, c, b, a)
and
(a, b, c, d, a) and (a, d, c, b, a)
(a, b, d, c, a) and (a, c, d, b, a)
(a, c, b, d, a) and (a, d, b, c, a)
are same cycles.
So, total number of distinct cycles are (15 × 3) = 45.