SPOJ PPATH, Convert a given 4-digit prime to another four-digit number

Question

In the SPOJ PPATH problem, we are given two four-digit primes, and we need to convert as little as possible, the first stroke to the second, changing one digit at a time, and at each step the number should be prime. We should output “IMPOSSIBLE” if primes cannot be converted in this way.

However, solutions to the problem in which the impossible case was not even considered were adopted, which leads to the assumption that each four-digit prime can be converted to any other four-digit number in the indicated order. I could not prove it. It's true? How can we prove this formally? Also, is there a general result for n-bit primes?

Answer 1

For a four-digit number, this can be checked exhaustively through the program, but for n digits we will have to theoretically prove this.

Answer 2

So, you have an undirected graph with vertices as simple 4-digit numbers and edges connecting two numbers that differ by 1 digit. You are asked to find the closest path from one peak to another. IMPOSSIBLE result will be created if you cannot find such a path. This would mean that the graph has more than one connected component. If you prove that this graph has one connected component, it guarantees the existence of a path.

I do not know how to prove this formally, but it is very easy to check whether the graph described above has only one component. You can write an algorithm, and its result can be interpreted as evidence for a specific case of four-digit graphs.