Prove that a "prime graph" is Bipartite.

Question

Let the prime graph be defined as the graph of all natural numbers, with two vertices being connected if the sum of the numbers on the two vertices add up to a prime number. Prove that the prime graph is Bipartite.

Answer 1

Hint: The natural numbers must not include $0$. Consider odd and even numbers.