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 consisting whose vertices are the points {-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.

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.

Given a Turing machine T, let G_T be the graph consisting of all points (s,h) ∈ ℕ² such that either h = 1 and T halts in fewer than s steps, or h = 0 and T does not halt in fewer than s steps. And (x,y) is connected to (x',y') iff y = y'. Clearly, the automorphism group of G_T acts with finite quotient.

Note that (0,0) is always a point since no Turing machine halts in fewer than 0 steps, so the graph G_T is connected if and only if T never halts. Since the halting problem is undecidable, there is no algorithm that will uniformly decide whether G_T 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 consisting whose vertices are the points {-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.