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 connected.
This has no solution on the textbook. How should I approach this problem? I'm thinking of proving everything is connected via some path to $1$ but I don't know how to do that.
Daniel hinted Bertrand's postulate. Since it was proven by Chebyshev, it's actually a theorem.
Let all nodes $1,\dots,n-1$ be connected to $1$. We observe $n$. By Bertrand-Chebyshev theorem, there is a prime $p$ such that $n < p < 2n$. So, we can write
$$p = x + n, \quad \text{for some $x < n$}.$$
So, nodes $x$ and $n$ are connected. However, by the assumption, $x$ is connected to $1$, which means that $n$ is also connected to $1$.
This is an overkill, but you can show something stronger: it is possible to go between any two vertices in an uniformly bounded number of steps, i.e. there is a constant $K$ such that any two vertices are connected by a path of length at most $K$.
A natural $a$ is called a Polignac number if there are infinitely many pairs of primes whose difference is $a$.
Assume $y>x$. Note that you can go from $x$ to $y$ in two steps if there's $z$ such that $x+z,y+z$ are prime. As an important case, you can go from $x$ to $y$ if $y-x$ is a Polignac number.
Pintz has recently shown (page 3) that there's a constant $C$ such that every interval $[n,n+C]$ contains a Polignac number.
To prove that there's a path from $x$ to $y$, take a Polignac number $x-a \in [x-C,x]$ and go from $x$ to $a$ (note their difference is a Polignac number and $a \leq C$). Likewise, go from $y$ to $b$ (where $b \leq C$).
Now you need to connect $a$ to $b$, where both numbers are bounded by $C$. You can do this in a bounded number of steps via the Bertrand's postulate.
