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

couldthere be?What is the probability that a particular $m$-clique happens.

Put it together using the Linearity of Expectation.