Dtyjlui

If a connected graph has $e$ edges, $v$ vertices, and $e > 3(v - 2)$, then the graph is nonplanar. If the graph is also triangle-free, then it is nonplanar if $e > 2(v - 2)$. Such graphs are "obviously" nonplanar, because you just have to count simple things about them. How many nonplanar graphs of with $v$ vertices are obviously nonplanar?

More precisely, let $N_n$ be the set of nonplanar, connected graphs on $n$ vertices, and $E_n$ the set of nonplanar graphs on $n$ vertices such that $e > 3(v - 2)$ or $e > 2(v - 2)$ if the graph is triangle-free. Is there anything that we can say about the asymptotics of $|E_n| / |N_n|$?

Using the geng program in the nauty distribution I computed $|E_n| / |N_n|$ for $5 leq v leq 10$. The sequence of proportions begins like this:

begin{align*}
frac{|E_5|}{|N_5|} &= frac{1}{1} = 1 \
frac{|E_6|}{|N_6|} &= frac{5}{13} = 0.385 \
frac{|E_7|}{|N_7|} &= frac{42}{207} = 0.203 \
frac{|E_8|}{|N_8|} &= frac{849}{5143} = 0.165 \
frac{|E_9|}{|N_9|} &= frac{37980}{189185} = 0.201 \
frac{|E_{10}|}{|N_{10}|} &= frac{3386986}{10663766} = 0.318 \
end{align*}

This isn't much data, but it made me wonder if there were any real results.

The ratio you're looking at tends to $1$ as $n$ goes to $infty$, though this is extremely non-obvious from small examples.

The reason is that, of the $2^{binom n2}$ graphs on $n$ (labeled) vertices, almost all have average degree close to $frac n2$: that is, they have close to $frac12binom n2$ edges. This happens because the number of such graphs with $e$ edges is $binom{binom n2}{e}$, and a near-central binomial coefficient (when $e approx frac12binom n2$) is much larger than one where $e$ is far from $frac12binom n2$. There are many inequalities that quantify this, such as Chernoff's inequality; the broad idea is that $binom{N}{N/2 pm t}$ is about an $e^{-t^2/N}$ fraction of $binom{N}{N/2}$, so it's relatively small when $t gg sqrt N$.

But if we're looking at graphs with $e le 3(n-2)$, then the average degree is a bit less than $6$. This, as we see above, is very atypical for $n$-vertex graphs. So almost all graphs are non-planar, because almost all graphs are obviously non-planar. Of course, for $n=1,dots,10$, $frac n2$ is smaller than $6$, so this doesn't come up.

(For isomorphism classes on graphs - if we don't count two labelings of the same graph twice - the same thing happens, because almost all graphs have no nontrivial automorphisms. Therefore there are approximately $2^{binom n2}/n!$ isomorphism classes of $n$-vertex graphs, and again almost all of them are obviously non-planar.)

It might be more interesting to look at the opposite ratio. Let $bar{E}_n$ be the set of connected $n$-vertex graphs with at most $3(n-2)$ edges, and let $P_n$ be the set of all $n$-vertex planar graphs. What can we say about the ratio $frac{|P_n|}{|bar{E}_n|}$ - the fraction of not-obviously-nonplanar graphs that actually turn out to be planar?

I'm not quite sure, but I expect this ratio to tend to $0$. Almost all graphs in $bar{E}_n$ have exactly $3(n-2)$ edges (intuitively, given a graph with fewer edges than that, there are very many ways to complete it to exactly $3(n-2)$ edges). But I expect that most connected graphs with exactly $3(n-2)$ edges have some low-degree vertices. Say there's a vertex of degree $1$. Then removing it produces a graph with $n-1$ vertices and $3n-7 > 3(n-3)$ edges - an obviously non-planar graph.

If almost all connected graphs on $3(n-2)$ edges have a vertex of degree $1$ or $2$, then almost all graphs in $bar{E}_n$ are not in $P_n$.

So, to summarize; if we play a game where I give you randomly chosen $1000$-vertex graphs and you try to use the number of edges to predict if they're planar or not - you'll almost always get it right. But you'll be right only because the graphs will almost always be very very obviously non-planar. In the rare cases when the number of edges leads you to think that a graph might be planar, it almost always won't be.

To add to @Misha 's answer, for each positive integer $k geq 3$, even almost all $k$-regular graphs are nonplanar.

Almost all such graphs $G$ on $n$ vertices are good expanders: The number of vertices that need to be removed from $G$ so that every component in the remaining graph has no more than say $frac{n}{3}$ vertices is $theta(n)$. For planar graphs, it suffices to remove $O(sqrt{n})$ vertices.