3
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is very surprising to learn! Where can I see the "almost all"-arguments fleshed out? For instance, why do almost all graphs have average degree close to $n / 2$? $\endgroup$ – rwbogl Jan 9 '19 at 19:25
  • 2
    $\begingroup$ Such "almost-all" arguments come from the study of random graphs; see for example this textbook. (It's easier to work with the statement "a random graph almost always has this property" than "almost all graphs have this property" because we get to use the tools of probability, but the two statements are equivalent.) I've edited my answer to flesh out the specific claim about average degree. $\endgroup$ – Misha Lavrov Jan 9 '19 at 20:22
  • $\begingroup$ thank you very much for the book reference :D $\endgroup$ – SK19 Jan 12 '19 at 6:56
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.