Deciding when an infinite graph is connected

My original example was not locally finite, this is a different example which is locally finite.

Given a Turing machine T, let G_T be the graph whose vertex set is {-1,+1}×ℤ, and (a,n) is connected to (b,m) if and only if either a = b and |m-n| = 1, or a ≠ b and T halts (with blank input) in exactly |m - n| steps. This is computable since it is decidable whether T halts in a given number of steps. The automorphism group of G_T acts transitively since the maps (a,n) → (±a,n+k) are always automorphisms. The graph G_T is connected if and only if T eventually halts. Since the halting problem is undecidable, there is no algorithm that will uniformly decide whether G_T is connected.