Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices ...

Question

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

Accepted Answer

C. 7 We have a random graph on 8 vertices where each possible edge appears independently with probability 1/2. A cycle of length 3 (triangle) requires choosing 3 vertices and all 3 edges among them to be present. Using linearity of expectation, we count the expected number of triangles by multiplying the number of ways to choose 3 vertices by the probability that all 3 edges among them are present.

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