GATE CSE 2013 | Question: 24

Question

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

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

Comments

Whats the random variable and the sample space?

Is it no. of graph with 3 length cycle or different ways in which we can select 3 vertex out of 8 vertex in same graph?

Answer 1

for creating a triangle  we need 3 vertices we have n vertices choose one in nc1 ways .as the probability of edge on that vertex is 1/2, so 1/2* nc1.

again from remaining n-1 vertices choose one with probability  1/2 i.e 1/2*n-1c1 .again from n-2 choose one i.e 1/2*1/2*1/2*n*(n-1)*(n-2) now divide it with 3! as it is unordered graph.

i.e 1/2*1/2*1/2*n*(n-1)*(n-2)/3!  put n=8 you get your answer.

Answer 2

Random Variable X =  Number of unordered cycles of length three

Asked (E(X))

We can have X=0,1,2,3,4 also, why are we considering only one triangle?