# Number of unordered cycles of length $3$ in a graph with $n$ vertices.

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of unordered cycles of length $3$?

The solution is given but I find it difficult to understand. It is as follows -

There can be total $^8C_3$ ways to pick $3$ vertices from $8$. The probability that there is an edge between two vertices is $\frac{1}{2}$. So expected number of unordered cycles of length 3$=\, ^8C_3\times(\frac{1}{2})^3 = 7$.

Why did they cube $\frac{1}{2}$?

The way I approached is that with $8$ vertices, the maximum n umber of edges possible is $^8C_2=28$, since the probability of edges occurring between a pair of vertices is $0.5$, therefore the number of edges present = $28\times0.5=14$. This was all I could do and got stuck here. How did they solve it? Probability always confuses me so a detailed explanation would be really appreciated.

• Focus on 3 vertices $a,b,c$. They form a triangle only when their 3 possible edges $ab, ac, bc$ are present. Because all edges are picked independtly, that's $P(ab$ is an edge AND $ac$ is an edge AND $bc$ is an edge$) = P(ab$ is an edge$) \cdot P(ac$ is an edge$) \cdot P(bc$ is an edge$) = 1/2 \cdot 1/2 \cdot 1/2$. And that's actually the expected number of triangles per 3-vertices, and the proof follows from linearity of expectation. – Manuel Lafond Feb 2 '15 at 16:34
• Please make this an answer so that people with similar doubts will know! – Siddharth Thevaril Feb 2 '15 at 16:44
• As you wish good sir :) – Manuel Lafond Feb 2 '15 at 16:56

Focus on 3 vertices $a,b,c$. They form a triangle only when their 3 possible edges $ab,ac,bc$ are present. Because all edges are picked independently, that's $P(ab$ is an edge AND $ac$ is an edge AND $bc$ is an edge$)=P(ab$ is an edge$)⋅P(ac$ is an edge$)⋅P(bc$ is an edge$)=1/2⋅1/2⋅1/2$. And that's actually the expected number of triangles per 3-vertices, and the proof follows from linearity of expectation.

Let's go with the gory details :)

Denote by $T$ the number of triangles of the graph $G$, and by $V_3 = {V(G) \choose 3}$ the set of possible triplets of vertices. Finally for $\{a,b,c\} \in V_3$,let $I_{a,b,c} = 1$ if $a,b,c$ form a triangle, and zero otherwise.

Then,

$$\mathbb{E}(T) = \mathbb{E}(\sum_{\{a,b,c\} \in V_3}I_{a,b,c}) = \sum_{\{a,b,c\} \in V_3} \mathbb{E}(I_{a,b,c}) = \sum_{\{a,b,c\} \in V_3} \frac{1}{2^3} = {|V(G)| \choose 3} \cdot \frac{1}{2^3}$$

• Pardon me... but I have a basic question.. .What are un-ordered cycles / ordered-cycles in a graph ? – SimpleGuy Dec 1 '17 at 3:34

By the linearity of expectation, the expected number of triangles is ${8\choose 3}$ times the expected number of triangles on a subgraph on (any) three vertices. The expected number of triangles on that subgraph is $(1/2)^3=1/8$; either there is or there isn't -- in order to have a triangle, all three edges must be present.