On the non-planarity of a random subgraph

Abstract

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.

arXiv commentFinal version