# Condition for Connectedness of Graph of Prime Numbers Differing in only $1$ Digit

(This question is inspired by the StackOverflow question Converting prime numbers by @Manas, which turns out to be the problem PPATH of SPOJ.)

Let's construct a graph $G$ of all primes $p$ having $L$ digits in base-$n$. Two primes $p$ and $q$ form an edge in $G$ iff they only differ in $1$ digit (e.g. $1\mathbf{0}09$ and $1\mathbf{1}09$ form an edge).

Is there some (approximated?) condition on $n$ and $L$ that $G$ is connected?

For example, it seems that when $n$ is odd $G$ is usually disconnected, while when $n$ is even ($>2$) $G$ is usually connected.

-

I think Terry Tao's paper might help here: http://arxiv.org/abs/0802.3361

It shows that the isolated primes are of positive relative density. I'm not sure if the method can be extended to show that there are large connected blocks.

-

This question seems fairly advanced. You may want to consider asking it on MathOverflow.

-