6
$\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$

1 Answer 1

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$
4
  • $\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
    Commented Oct 2, 2018 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$ Commented Oct 2, 2018 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
    Commented Oct 2, 2018 at 21:34
  • $\begingroup$ @j0equ1nn I think it is a great idea. $\endgroup$ Commented Oct 2, 2018 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .