# Simple undirected Graph question with probability

Suppose that a random (simple, undirected) graph $G = (V, E)$ on a set of $n = 10$ vertices $V = \{v_1, . . . , v_n\}$ is constructed using the following random process: independently for each pair of vertices $v_i$, $v_j$ , $i \neq j$, with probability $1/2$ the edge $\{v_i, v_j\}$ is in the edge set $E$ (and with probability $1/2$ it is not in $E$).

A triangle inside a graph is any set of three distinct vertices such that there is an edge between every pair of them.

i. What is the expected number of triangles inside such a random graph on $10$ vertices? [5 marks]

ii. Prove that the probability that this random graph contains at least $45$ different triangles is at most $1/3$. (You may quote and use any theorem that we have proved in lectures.) [10 marks]

So I'm only on part i) but I'm a little bit stuck. So I have $P(E) = 1/2$ and $P(\bar E) = 1/2$. So then I think I'm correct in saying $P(T)$, which is the probability that there is a triangle, is $1/2*1/2*1/2 = 1/8$? From there though I'm too sure where to go. Any hints?

• Whats with the instant downvote? Hardly helpful at all – BlackBruceLee Dec 4 '17 at 12:56

The probability of any particular triangle being present is $1/8$ as you say. Then by the linearity of expectation, you can get the expected number of triangles by multiplying $1/8$ by the total number of potential triangles.

This follows because we can think of the total number of triangles as the sum over possible triangles of the random variable which is $1$ if that triangle is present and $0$ otherwise. These variables are not independent, but that doesn't matter.

For the second part I suspect the result you're intended to quote is Markov's inequality.

• Thanks for the help. So would the potential number of triangles be $10C3$....? This gives me 120 triangles. So expected number of triangles is 15. – BlackBruceLee Dec 4 '17 at 13:18
• I think this is wrong, hence the -1. When you have triangles that share an edge, the probability of their occurence is not independent. – bat_of_doom Dec 4 '17 at 13:20
• Oh okay, I see. Well now I'm not too sure what to do – BlackBruceLee Dec 4 '17 at 13:21
• @bat_of_doom No, it's not wrong. The events are not independent, but they don't need to be. Google "linearity of expectation" for an explanation. – Especially Lime Dec 4 '17 at 13:29
• @BlackBruceLee yes, you're correct with $15$. – Especially Lime Dec 4 '17 at 13:30