Let $Z_m$ be a random variable that corresponds to the number of $m$-cliques in a random graph with n vertices and the probability of any edge happening is 1/2. Prove that $$ \mbox{E}[Z_m] = {n \choose m} 2^{-{m \choose 2}}.$$
[Math] Expected number of m-cliques in a random graph
graph theoryprobabilityrandom-graphs
Best Answer
What is an $m-$clique?
How many $m$-cliques could there be?
What is the probability that a particular $m$-clique happens.
Put it together using the Linearity of Expectation.