Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $\dfrac{1}{2}.$ What is the expected number of unordered cycles of length three?
Answer is (C)
A cycle of length $3$ requires $3$ vertices. Number of ways in which we can choose $3$ vertices from $8$ = $^{8}C_{3} =56.$ Probability that $3$ vertices form a cycle $=\text{ Probability of edge between vertices 1 and 2}\times \text{ Probability of edge}$ $ \text{between vertices 2 and 3} \times \text{Probability of edge between vertices 1 and 3}$ $=\dfrac{1}{2}\times \dfrac{1}{2}\times \dfrac{1}{2} =\dfrac{1}{8}$ So, expected number of cycles of length $3 = 56\times \dfrac{1}{8} = 7$ [email protected] http://stackoverflow.com/questions/14801072/number-of-cycles-in-a-random-graph
can we model like this ?
@Debashish_Deka How are you writing in Blue color ?
..................
@Arjun Sir, What is the significance of word "unordered cycle" here... What would be the answer if it asked for Number of Ordered Cycles?
If it were ordered cycles then total possibilities out of 56 will be 8 (123,234,...678,781,812)?
So expected number of cycles of length 3 will be 8 x $\frac{1}{8}$ = 1
please verify.
@Arjun sir why are we not considering circular permutations of vertices here?