GATE 2013 CS (CS1) – Question 34
An undirected random graph has eight vertices, each possible edge independently present with probability one half. Find the expected number of unordered triangles.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) 7
Explanation
There are $\binom83=56$ triples of vertices. A triple forms a triangle exactly when all three edges exist, probability (1/2)³=1/8. By linearity of expectation the expected count is 56/8=7, C; triangle events need not be independent for this sum.