Prime parallel rows for the first 20 numbers

Question

Two positive integers can be joined with a straight segment if their sum is a prime and the segment doesn't intersect any other segments. What is the most number of pairs you can join if you can place numbers from 1 to 20 in two parallel rows?

Answer 1

20 09 08 03 10 19 12 05 06 07
17 14 15 16 13 18 11 02 01 04

This results in

28 pairs.

Note that

no triangle allowed.

---

A proof of optimality:

Without loss of generality, assume that the two rows are located on integral points on the plane, on the lines $y = 0$ and $y = 1$, respectively. Also assume that the points on each row are consecutive (e.g. from $(0, 0)$ to $(9, 0)$, etc.).

Connect all the pairs. This creates a planar graph. Let $e$ be the number of edges (i.e. line segments), and let $g$ be the number of "holes", i.e. loops created by the line segments. These are called "faces" in the link cited below.

We then have Euler's formula, which states $20 - e + g = 1$ (note that our definition of $g$ excludes the outer, infinitely large region).

So it suffices to show that $g \leq 9$. But we know that the area of each "hole" is a half integer (e.g. by Pick's theorem), and their sum is $\leq 9$ (the area of the convex hull, which must have area $9$, again by Pick's theorem).

Moreover, since triangles are not allowed, no hole can have area $\frac{1}{2}$ (again by Pick's theorem), and hence every hole has area $\geq 1$.