Fibonacci Divisibility Graph

The answer is 29.

First, the Fibonacci numbers have the property that $F_a | F_b$ if and only if $a|b$ . Thus, we can construct a graph with $3, 4, 5, \ldots, N$ instead of $F_3, F_4, F_5, \ldots, F_N$ , apply the same divisibility rule (an edge if a vertex is multiple of the other), and obtain an isomorphic graph.

With this, the following is a planar embedding for $N = 29$ , with labels $3,4,\ldots,N$ instead of $F_3,F_4,\ldots,F_N$ :

Now, showing that $N \ge 30$ is impossible is actually simpler. By Kuratowski's theorem , a graph is not planar if and only if there exists a subgraph of it isomorphic to a subdivision of either $K_5$ or $K_{3,3}$ . We claim there exists a subgraph isomorphic to a subdivision of $K_{3,3}$ . This is best shown by a picture:

Thus no $N \ge 30$ will make it planar (because it will contain the above subgraph), so the largest $N$ is $\boxed{29}$ .