Consider the graph $\mathcal{G}_{n}$ whose vertices are the integers from 1 to $n$. Two points $a$ and $b$ are connected if and only if $a+b$ is prime. For which $n$ is the graph $\mathcal{G}_{n}$ planar?

## Paths on graphs

Definition 3. A graph is said to be Eulerian if there exists a path that passes through each edge exactly once. A graph is said to be Hamiltonian if there exists a path that passes through each vertex exactly once.

## Theorem

A graph is Eulerian if and only if the number of vertices of odd degree is either 0 or 2.
It is possible to draw $\mathcal{G}_{8}$ in the plane, but arranging $\mathcal{G}_{9}$ can result in the graph of the three houses and three factories, which is not planar.
![](https://cdn.mathpix.com/cropped/2024_05_10_7286ba4d154441c7d078g-67.jpg?height=480&width=1436&top_left_y=356&top_left_x=173)