How many graphs are "obviously" nonplanar?

156 Views Asked by At

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.

2

There are 2 best solutions below

3
On BEST ANSWER

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 $\frac12\binom 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 \frac12\binom n2$) is much larger than one where $e$ is far from $\frac12\binom 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.

0
On

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.