On the Non-Planarity of a Random Subgraph

2013-06-24T00:00:00Z (GMT) by Alan Frieze Michael Krivelevich
<p>Let <em>G</em> be a finite graph with minimum degree <em>r</em>. Form a random subgraph <em>G<sub>p</sub> </em>of <em>G</em> by taking each edge of <em>G</em> into <em>G<sub>p</sub></em>independently and with probability <em>p</em>. We prove that for any constant ε > 0, if , then <em>G<sub>p</sub> </em>is non-planar with probability approaching 1 as <em>r</em> grows. This generalizes classical results on planarity of binomial random graphs.</p>