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?

- $\dfrac {1}{8}$
- $1$
- $7$
- $8$

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] http://stackoverflow.com/questions/14801072/number-of-cycles-in-a-random-graph

0

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 .

45

- 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 ?

0

@ 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?

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?

0

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

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.

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.

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.

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.