I am interested in algorithms that help decide whether a *countably infinite locally finite * graph is connected.

I think there is no algorithm that works for all graphs, e.g. no algorithm should work for an infinite chain with one edge removed.

I care about a specific graph $\Gamma$ whose automorphism group acts with finite quotient, i.e. there are only finitely many orbits of vertices. Also $\Gamma$ can be realized as an explicit collection of points in $\mathbb R^n$, and there is an easily computable function $d:\mathbb R^n\times \mathbb R^n\to \mathbb R$ such that two vertices $v,w$ are adjacent if and only if $d(v,w)=0$. I hope to find an algorithm that can be implemented so that after some computer experiments I would have evidence that the graph is actually connected.