I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere.
Prove: For sufficiently large $n$, the probability a random graph $G=(V,E)$ with $n$ vertices is planar is less than $2^{-0.49n^2}$.
I've ruled out using Kuratowski's characterization of planarity for proving this (since I know it's hard to determine whether or not a subgraph $G' \subset G$ is a topological $K_{3,3}$ or $K_5$. The other characterization I'm aware of is if a graph is planar, then $\exists v \in V$ such that $deg[v] \leq 5$. So the probability a random graph is planar is equivalent to $1-\mathbb{P}$ ,where $\mathbb{P} = $ the probability that a random graph has no vertices of degree less than or equal to 5.
However, I can't see how to proceed from this observation. Solutions/hints would be appreciated.
Best Answer
A random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (that's a necessary condition for planarity) is $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$ There are standard ways to estimate the sum.