SPOJ PPATH, Converting a given 4 digit prime to another 4 digit prime

Question

In the SPOJ problem PPATH we are given two four-digit prime numbers and we have to convert, in the least possible steps, the first prime into the second one by changing a single digit at a time and at each step the number should be prime. We have to output 'IMPOSSIBLE' if the primes cannot be converted in said fashion.

However, solutions to the problem in which the impossible case is not even considered have been accepted, which leads one to conjecture that every four-digit prime can be converted into any other four-digit prime in the specified manner. I was unable to prove it. Is it true? How can we prove it formally? Also, is there a general result for n-digit primes?

Answer 1

For four digit number this can be verified exhaustively through a program but for n digit we will have to prove it theoretically.

Answer 2

Well so you have an undirected graph with vertices as a prime 4-digit numbers and an edges connecting two numbers which differ in 1 digit. You are asked to find the closest path from one vertex to another. IMPOSSIBLE result will be produced if you will not be able to find such path. That would mean that graph has more than one connected component. If you prove that this graph has one connected component it will guarantee the existence of the path.

I don't know how to prove it in a formal way but it is very easy to check if graph described above has only one connected component. You can write an algorithm and its result can be interpreted as a proof for a specific case of 4-digit graphs.