Question : Given a graph that has $4$ nodes: $v_1, v_2, v_3, \text{ and } v_4$, such that there exists an edge between two nodes at a probability of $0.5$
(There isn't any dependence between the nodes being connected.)
A triangle in the graph is a set of $3$ nodes such that each $2$ of the them is connected by an edge.
- Calculate the probability that in the graph there will be no triangles.
- Find Expected number of triangles.
I am looking help in Question-$1$. Any help would be appreciated.
My Try
- I guess that probability that a random $3-$vertex subgraph will be a triangle will be $(0.5)^3$.
- And there will be $4 \choose {3}$, i. e. $4$ vertex with $3$ nodes.
Best Answer
Since there are $\ {4\choose2}=6\ $ possible edges in the graph, each of which may or may not be present, there are $\ 64\ $ possible graphs, each with a probability of $\ \frac{1}{64}\ $ of occuring. The entry in row $\ i\ $ and column $\ j\ $ of the table below lists the number of these graphs with $\ j\ $ edges that contain exactly $\ i\ $ triangles. \begin{array}{c|cccccc} &0&1&2&3&4&5&6\\ \hline 0&1&6&15&16&3&0&0\\ 1&0&0&0&4&12&0&0\\ 2&0&0&0&0&0&6&0\\ 3&0&0&0&0&0&0&0\\ 4&0&0&0&0&0&0&1 \end{array} From this table we see that there are a total of $\ 41\ $ of these graphs that contain no triangles. The probability of this occurring is therefore $\ \frac{41}{64}\ $.
The table also tells us that there are $\ 16\ $ graphs with $\ 1\ $ triangle, $\ 6\ $ with $\ 2\ $, and $\ 1\ $ with $\ 4\ $. The expected number of triangles is therefore $$ 1\times\frac{16}{64}+2\times\frac{6}{64}+4\times\frac{1}{64}=\frac{1}{2}\ . $$ An easier way of arriving at this last result is to use the linearity of expectations. There are $\ 4\ $ possible triangles, each of which has a probability of $\ \frac{1}{8}\ $ of being present, so the expected number present is $\ 4\times\frac{1}{8}=\frac{1}{2}\ $