## On the Non-Planarity of a Random Subgraph

journal contribution

posted on 24.06.2013 by Alan Frieze, Michael Krivelevich#### journal contribution

Any type of content formally published in an academic journal, usually following a peer-review process.

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*independently and with probability

_{p}*p*. We prove that for any constant ε > 0, if , then

*G*is non-planar with probability approaching 1 as

_{p}*r*grows. This generalizes classical results on planarity of binomial random graphs.