Number of H-free graphs on n vertices I'd like to get an estimate on the number of $H$-free graphs, i.e. graphs in which no set of $|V(H)|$ vertices induces a copy of $H$. There are results on this, but I have some problems in interpreting the probabilistic arguments.
For simplicity, let $H = K_3$, a triangle.
Let $G$ be a random graph on $n$ vertices in which each edge appears with probability $1/2$.
From this paper, we have that $Pr[G$ is $H$-free$] \leq e^{-c n^3/8}$ for some constant $c$ (see abstract, put $p = 1/2$ and $H = K_3$).
This probability seems very low, and I must be misinterpreting something.
Here's my problem.
Let $f(n)$ be the number of $H$-free graphs on $n$ vertices.
Then since $G$ is equally likely to be any graph on $n$ vertices, 
$$Pr[G\mbox{ is }H\mbox{-free}] = f(n)/2^{{n \choose 2}}$$
i.e. the number of $H$-free graphs divided by the total number of graphs.
But 
$$
f(n)/2^{{n \choose 2}} = Pr[G\mbox{ is }H\mbox{-free}] \leq e^{-c n^3/8}
$$
implies
$$
f(n) \leq 2^{n \choose 2}e^{-c n^3/8} < 1
$$
for large enough $n$.
Hence there are no triangle-free graphs. 
Where is the mistake?

The mistake occurs in the application of their theorem. You are right that any probability below $\frac{1}{2^{{n \choose 2}}}$ must be zero. But per their abstract, $M=n^2 p$ rather than $m=n^3 p^3$. 
