Given a graph that has $4$ nodes, $\exists$ edge between two nodes at probability of $0.5$, find probability that there will be no triangle in graph. 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.

 A: 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}\ $
A: Here is a solution to part $1$ via inclusion-exclusion.
We start by noting some facts about the graph.  The graph has $6$ potential edges in all.  There are $4$ potential triangles in the graph.  Of these, any single triangle has $3$ edges, any two triangles have a total of $5$ edges, any three have a total of $6$ edges, and the set of all four triangles has a total of $6$ edges.
Let $S_j$ be the total probability (with deliberate over-counting) of the configurations containing $j$ triangles, for $1 \le j \le 4$.  Then
$$\begin{align}
S_1 &= \binom{4}{1} 0.5^3 \\
S_2 &= \binom{4}{2} 0.5^5 \\
S_3 &= \binom{4}{3} 0.5^6 \\
S_4 &= \binom{4}{4} 0.5^6 \\
\end{align}$$
By the principle of inclusion-exclusion, the probability that the graph has no triangles is
$$1-S_1+S_2-S_3+S_4 = \boxed{41/64}$$
