5
$\begingroup$

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. enter image description here

$\endgroup$
5
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – j0equ1nn Oct 2 '18 at 21:27
  • $\begingroup$ @j0equ1nn but you will be able to show how they could isolate subsets to show a graph is non-planar by considering a subgraph. $\endgroup$ – Mark Bennet Oct 2 '18 at 21:30
  • $\begingroup$ @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! $\endgroup$ – j0equ1nn Oct 2 '18 at 21:34
  • $\begingroup$ @j0equ1nn I think it is a great idea. $\endgroup$ – Mark Bennet Oct 2 '18 at 21:37

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.