On the non-planarity of a random subgraph
  Let $G$ be a finite graph with minimum degree $r$. Form a random subgraph $G_p$ of $G$ by taking each edge of $G$ into $G_p$ independently and with probability $p$. We prove that for any constant $\epsilon>0$, if $p=\frac{1+\epsilon}{r}$, then $G_p$ is non-planar with probability approaching 1 as $r$ grows. This generalizes classical results on planarity of binomial random graphs. 
Alan Frieze, Michael Krivelevich
math.CO