Log In
38 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
edited by

3 Answers

85 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]

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?

19 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.
Please anyone explain " there are 8 possibilities of having edges with 3 vertices and only one among them will have 3 edges which form a cycle."   this line.......
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.

Related questions

18 votes
2 answers
Suppose $p$ is the number of cars per minute passing through a certain road junction between $5$ PM and $6$ PM, and $p$ has a Poisson distribution with mean $3$. What is the probability of observing fewer than $3$ cars during any given minute in this interval? $\dfrac{8}{(2e^{3})}$ $\dfrac{9}{(2e^{3})}$ $\dfrac{17}{(2e^{3})}$ $\dfrac{26}{(2e^{3})}$
asked Aug 7, 2014 in Probability gatecse 3.7k views
40 votes
4 answers
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is $3$ $4$ $5$ $6$
asked Nov 3, 2014 in Probability Ishrat Jahan 7.4k views
23 votes
4 answers
When a coin is tossed, the probability of getting a Head is $p, 0 < p < 1$. Let $N$ be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of $N$ is $\dfrac{1}{p}$ $\dfrac{1}{(1 - p)}$ $\dfrac{1}{p^{2}}$ $\dfrac{1}{(1 - p^{2})}$
asked Oct 31, 2014 in Probability Ishrat Jahan 3.1k views
27 votes
5 answers
If the difference between the expectation of the square of a random variable $\left(E\left[X^2\right]\right)$ and the square of the expectation of the random variable $\left(E\left[X\right]\right)^2$ is denoted by $R$, then $R=0$ $R<0$ $R\geq 0$ $R > 0$
asked Sep 29, 2014 in Probability jothee 3.3k views