# What's the first non-planar graph of the first $n$ numbers where edges show divisibility?

Let $$G_n$$ be a graph with vertices $$v_1, v_2, v_3,\dots, v_n$$, where there is an edge between $$v_i$$ and $$v_j$$ if and only if either $$v_i$$ divides $$v_j$$ or vice versa. Is there a value $$n$$ such that $$G_n$$ is non-planar, ie cannot be drawn in the plane without intersecting edges? If so, what is the least value of $$n$$ for which this happens? By way of example, the drawing below shows that $$G_{12}$$ is planar.

## 1 Answer

$$G_{14}$$ is planar: From your $$G_{12}$$ sketch, relocate $$7$$ into the $$1{-}2{-}6$$ triangle. This allows you to add $$14$$ with edges to $$1$$, $$2$$, an $$7$$. And the prime $$13$$ can be placed anywhere in the outer region.

One readily sees that the five numbers $$1,2,4,8,16$$ form a $$K_5$$, hence $$G_{16}$$ is not planar.

So what about $$G_{15}$$? It turns out, we would have a $$K_{3,3}$$ with vertices $$1,2,3$$ and $$6,12,m$$ if there were another common multiple of $$2$$ and $$3$$ available. While there is no such $$m$$, we have $$5$$, which is indirectly linked to $$3$$ via $$15$$ and to $$2$$ via $$10$$. Therefore $$G_{15}$$ is not planar.

• Very nice proof. We're going to mess around with this with some 3rd and 4th graders next week and see if they can figure this out. (Of course, their answer won't look quite like yours!) If they like the problem, we'll dip deeper into graph theory later in the program. – j0equ1nn Oct 2 '18 at 21:27
• @j0equ1nn but you will be able to show how they could isolate subsets to show a graph is non-planar by considering a subgraph. – Mark Bennet Oct 2 '18 at 21:30
• @MarkBennet I'm thinking similarly. It will take them a while to develop the notion of looking for small non-planar graphs, and then looking for instances of it as a subgraph. But they will be discovering all this from scratch. It is really fun to watch that happen, one just has to know what to say and especially what not to say! – j0equ1nn Oct 2 '18 at 21:34
• @j0equ1nn I think it is a great idea. – Mark Bennet Oct 2 '18 at 21:37