The Gateway to Computer Science Excellence
+31 votes

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?

  1. $\dfrac {1}{8}$
  2. $1$
  3. $7$
  4. $8$
in Probability by Veteran (430k points)
edited by | 5.4k views

3 Answers

+81 votes
Best answer

Answer is (C)

A cycle of length $3$ requires $3$ vertices.

Number of ways in which we can choose $3$ vertices from $8$ = $^{8}C_{3} =56.$

Probability that $3$ vertices form a cycle $=\text{ Probability of edge between vertices 1 and 2}\times \text{ Probability of edge}$
$ \text{between vertices 2 and 3} \times \text{Probability of edge between vertices 1 and 3}$

$=\dfrac{1}{2}\times \dfrac{1}{2}\times \dfrac{1}{2} =\dfrac{1}{8}$

So, expected number of cycles of length $3 = 56\times \dfrac{1}{8} = 7$

[email protected]

by Veteran (430k points)
edited by
Sir , is there any significance of the term "expected" here , since I am unable to see anywhere the usage of random variable , so the question is actually just asking for the calculation of no of cycles in the graph with 8 vertices .
presence of an edge is given by a random variable- so expectation is important.
  • To count the no of triangles we need to scan the entire graph taking 3 points at a time. So no of experiments = $\binom{8}{3}$
  • Each such experiment result can either be a triangle (with prob p = $\frac{1}{8}$) or no triangle (with prob q = $\frac{7}{8}$ )
  • So, Binomial distribution with $E$ = $\text{np}$

can we model like this ? 


@Debashish_Deka  How are you writing in Blue color ?



@ arjun sir, i did not understand your solution.
please  correct me if i am wrong.
here the number of cycles of length three is asked on average if we take a random graph of 8  vertices.
shouldnt the random variable taken be number of cycles of length three in a graph?
i think number of cycles of length 3 is acting as random variable here

@Arjun Sir, What is the significance of word "unordered cycle" here... What would be the answer if it asked for Number of Ordered Cycles?


If it were ordered cycles then total possibilities out of 56 will be (123,234,...678,781,812)?

So expected number of cycles of length 3 will be 8 x $\frac{1}{8}$ = 1

please verify. 

ur method is correct but is there some term like ordered cycles in a graph ??
Why it cant be 8p3/8 for ordered cycles plzz tell me

@Arjun sir why are we not considering circular permutations of vertices here?

+18 votes
Maximum number of cycles of length 3 from 8 vertices = C(8,3) = 56.

It is a Binomial experiment as we keep on repeating the same Bernouli experiment again and again. What Bernouli experiment we keep on repeating ? We keep on checking all 56 possibilities whether there is a cycle or not. Checking is clearly a Bernouli experiment because after checking we will either find cycle (success) or no-cycle(failure).

So number of Bernouli experiments, n = 56.

Let X be a random variable which indicates number of 3-length cycles.

Expectation (X) (i.e) Expected number of 3-length cycles = n * p (since it is a Binomial distribution)

                             where n is number of Bernouli trials or experiments and p is probability of success (i.e) probability of getting a 3-length cycle in 1 Bernouli experiment. p = 1/8 as there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle.

    So Expectation (X) = n * p

                                   = 56 *  1/8

                                   = 7.
by Loyal (8k points)
0 votes
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.
by (41 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
104,650 users