Let $G$ be the graph on $\Bbb N$ such that there is an edge between $n$ and $m$ when $|n-m|$ is prime. Can we color $G$ with a finite number of colors

Question

When I read a book about graph theory , I found the four color theorem and this question about a infinite graph arose.

Let $G$ be a graph whose vertices are the natural numbers and where $n$ and $m$ are joined by an edge if and only if $\lvert m - n \rvert$ It is a prime number. Can you color $G$ with a finite number of colors?

I managed to paint 40 vertices with 9 colors and it seems to stabilize, but I could not prove anything.

Answer 1

The chromatic number is $4$. Coloring each residue mod 4 the same color shows that 4 colors is sufficient. There is no 3-coloring, as $5,7,10,12$ is a $K_4$.