Project ForgeDiscrete Mathematics
Graph Theory
GATE 2013
Medium
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?
- A1/8
- B1
- 7
- D8
Explanation
There are C(8,3) = 56 possible unordered vertex-triples, each a candidate triangle. A given triple forms a triangle only if all 3 of its edges are present, each independently with probability 1/2, so P(triangle) = (1/2)³ = 1/8. By linearity of expectation, the expected number of triangles = 56 × 1/8 = 7.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.