# Proving that a “prime graph” is connected

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.

-
If you know that Bertrand's postulate is true, you know that each $n > 1$ is connected to a $k < n$. That suffices. – Daniel Fischer Aug 1 '13 at 21:59
What is that? I haven't learned anything like that. – user54609 Aug 1 '13 at 22:01
Bertrand's postulate says that for all $n > 1$, there is a prime between $n$ and $2n$. You can see how that helps, can't you? Without that, I don't see an immediate easy proof. – Daniel Fischer Aug 1 '13 at 22:04

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$.

-
Hmm. I wonder why induction is so useful in graph theory - I should really start using it more rather than crutching everything using proofs by contradiction (which also seem to appear way more often in graph theory). – user54609 Aug 2 '13 at 1:45
Induction is useful when you can reduce a case to a "simpler" one (assuming there is such a thing as the "simplest" case). This has nothing to do with the graph theory per se, but with the nature of the statement being proven. You may argue that many graphs of type "for $n$ vertices graph looks like this" can be reduced to their subgraphs (fitting the same description) by simple operations, and in such cases induction is natural. – Vedran Šego Aug 2 '13 at 1:50

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.

-
And if Polignac's conjecture is true, then $K=3$ and this bound is tight. – Tomas Aug 2 '13 at 9:45