Consider an undirected random graph of eight vertices. The probability that…
20132013
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
- A.
1/8
- B.
1
- C.
7
- D.
8
Attempted by 178 students.
Show answer & explanation
Correct answer: C
Key idea: count all unordered triples of vertices and multiply by the probability that all three edges in a triple are present.
Number of unordered triples of vertices: C(8,3) = 56.
Probability a given triple forms a triangle: (1/2)^3 = 1/8, since the three edges must each be present independently.
Expected number of unordered 3-cycles = 56 * 1/8 = 7.
Answer: 7
A video solution is available for this question — log in and enroll to watch it.