Expected number of triangles in G(n,m) |

Consider picking a graph with m edges on n vertices uniformly at random from the set of all graphs with n vertices and m edges. What is the expected number of triangles? Before we give an exact formula, consider the following heuristic. We can approximate this graph with a random binomial graph $G(n,p)$ (each edge appears independently from the others with probability $p$ ) where $p=\frac{m}{{n \choose 2}}\approx \frac{2m}{n^2}$ . Therefore the expected number of triangles $T$ in $G$ should be roughly $E[T]=p^3{n \choose 3}\approx\frac{8m^3}{n^6}\frac{n^3}{6}\sim \frac{4m^3}{3n^3}$ . This heuristic can be turned into a rigorous statement by using the asymptotic equivalence of the two random graph models. However this is a good asymptotic approximation. What about an exact formula? The simplest way is counting! How many graphs (let me mention even a bit late that we are talking about labelled graphs, which means that we have names for the vertices. For convenience we call the names by the integers 1 through n) on n vertices do we have? Clearly ${{n \choose 2} \choose m}$ . Consider now a triangle formed by three distinct vertices $i,j,k$ . What is the probability of seeing this particular triangle? We have to count how many graphs contain it and divide by the total number of possible graphs. Clearly we have to use 3 edges and therefore the way of placing the rest of the edges is ${{n \choose 2}-3 \choose m-3}$ . The expectation therefore is $E[T]={n \choose 3}\frac{{{n \choose 2}-3 \choose m-3}}{{{n \choose 2} \choose m}}$ . QED