5.4k views

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$

edited | 5.4k views

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

by Veteran (430k points)
edited
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 .
+10
presence of an edge is given by a random variable- so expectation is important.
+40
• 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 ?

+3

@Debashish_Deka  How are you writing in Blue color ?

+6

..................

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?
0
i think number of cycles of length 3 is acting as random variable here
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?

0

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

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

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

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)
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.

by (41 points)