A random graph with nodes is drawn by placing an edge with probability between and for all distinct and , independently. A triangle is a set of three distinct nodes that are all connected: there are edges between and , between and and between and .
(a) Let be the number of triangles in this random graph. Compute the maximum value and the expectation of .
(b) State the Markov inequality. Show that if , for some , then when
(c) State the Chebyshev inequality. Show that if is such that when , then when