A random graph with $n$ nodes $v_{1}, \ldots, v_{n}$ is drawn by placing an edge with probability $p$ between $v_{i}$ and $v_{j}$ for all distinct $i$ and $j$, independently. A triangle is a set of three distinct nodes $v_{i}, v_{j}, v_{k}$ that are all connected: there are edges between $v_{i}$ and $v_{j}$, between $v_{j}$ and $v_{k}$ and between $v_{i}$ and $v_{k}$.

(a) Let $T$ be the number of triangles in this random graph. Compute the maximum value and the expectation of $T$.

(b) State the Markov inequality. Show that if $p=1 / n^{\alpha}$, for some $\alpha>1$, then $\mathbb{P}(T=0) \rightarrow 1$ when $n \rightarrow \infty$

(c) State the Chebyshev inequality. Show that if $p$ is such that $\operatorname{Var}[T] / \mathbb{E}[T]^{2} \rightarrow 0$ when $n \rightarrow \infty$, then $\mathbb{P}(T=0) \rightarrow 0$ when $n \rightarrow \infty$