Considers an undirected random graph of eight vertices. The Probability that there is an egde between a pair of vertices is 1/2. What is the expected numbers of unordered of cycles length three.

Question

a) 1/8
b) 1
c) 7
d) 8
approach?

Answer 1

if itsAnswer option C) 7

There will be c(8,3) = 56 cycles.Probability of existence of a particular cycle is 1/2*1/2*1/2 =1/8.So no of cycles = 1/8*56 = 7.

Comments

Thanks.
@Arjun
Also is there any facility on this platform to upload photo of Question to be asked.

---

you got it rt?

Answer 2

Ans c

A cycle of length 3 can be formed with 3 vertices.

So number of ways we can form a cycle of length 3=3C3=1

 Number of ways to pick 3 vertices from 8 vertices=8C3=56

Total ways=56*1=56

 The probability that there is an edge between two vertices is 1/2.

Probability of existence of a particular cycle = 1/2*1/2*1/2

 So expected number of unordered cycles of length 3 = 56*(1/2)^3 = 7

Answer 3

Let me be slightly more formal (Answer is 7 btw)

S = Ordered set of all triplets of vertices

$S=\{(i,j,k):i,j,k \epsilon V,i\neq j\neq k\} \\ |S| = \binom{8}{3}=56$

Now I'll make random variable X such that $X_p((i,j,k))=\begin{cases} 1 & \text{ if i,j,k form a cycle} \\ 0& \text{ otherwise } \end{cases}$

Expected value of X will be the sum of all expectations of $X_p$ (by linearity theorem), which will give us the expected 3-cycles (by definition of $X_p$ above

$E(X)=E(X_1)+E(X_2)...E(X_{56})\\=56(1.p+0.(1-p))=56p$

Here p is the probability of finding a cycle in 3 vertices $i\rightarrow j \rightarrow k$

To find p, note by independence of events that $p(i\rightarrow j \rightarrow k)=p(i\rightarrow j ).p(j\rightarrow k).p(k\rightarrow i )\\=\frac{1}{2}.\frac{1}{2}.\frac{1}{2}=\frac{1}{8}$

Hence expected 3-cycles = 56p = 7 Q.E.D.