Graph Theory DM


#1

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
A. 15
B. 30
C. 90
D. 45


#2

6C4*(4-1)!/2

= 45

Option (D) is correct


#3

plzz give me some explanation about that.


#4

6C4 is the number of ways we can choose 4 vertices out of 6 vertices.

Now (4-1)!/2 is the number of ways we can arrange those 4 vertices. As they are in a circular closed path so we have to fix one node and permute the others. That’s why (4-1)!. and as both clock wise and anticlockwise would be same for a garland if reversed, so divided by 2.


#5

ThnkQ @Ruturaj . Now i remember the combinations…