Question

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}.$ What is the expected numbers of unordered cycles of length three?

• A. $\frac{1}{8}$
• B. 1
• C. 7
• D. 8

Answer 1

The correct option is C 7

We need to find unordered cycle of length 3 so we choose any 3 vertices from 8 vertices. This can be done in ${}^8{C}_3$ ways

To make cycle we need to choose edge between the selected vertices probability of choosing any edge is $\frac{1}{2}.$

So for three edges $=\frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}=\frac{1}{8}$

Expected no of cycle = np

Here, $n={}^8{C}_3\text{and}p=\frac{1}{8}$

Expected no of cycles $={}^8{C}_3\times \frac{1}{8}=7.$