Deciding when an infinite graph is connected

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.

• Igor, how about the following family of examples? \Gamma_n is the real line, with the usual graph structure, with every nth edge removed. It seems to me that these graphs are just as hard to distinguish from the real line as your example with just one edge removed, but the automorphism group now acts with finite quotient. – HJRW Apr 4 '10 at 15:45
• You need a way to bound the size of the quotient as Henry Wilton's comment shows. Another explanation: Consider all computable functions that can produce a graph whose nodes are indexed by $\mathbb Z$, and which is either real line or a segment $[-n,n]$ plus a bunch of isolated nodes ($n$ is arbitrary). You can not tell algorithmically functions of the first type from the second type, so you need a bound for $n$ as an input to your program. – Sergei Ivanov Apr 4 '10 at 16:19
• If you have only one graph, then there is a program. It is either "begin; print YES; end" or "begin; print NO; end", depending on your graph. – Sergei Ivanov Apr 4 '10 at 16:30
• Igor, when you "fix n" you are basically saying that you know the size of the quotient. That's why the quotient graph is relevant! – HJRW Apr 4 '10 at 16:31
• Actually the size of the quotient is not enough too. You cannot tell a line from a bunch of very long loops although both are homogeneous. – Sergei Ivanov Apr 4 '10 at 17:20

• Thanks! I really do not know much about the graph beyond what I stated. There is a closely related problem that is easier to explain. There the graph arises from a locally finite arrangement of hyperplanes in $\mathbb C^n$, where vertices correspond to hyperplanes, and two vertices are adjacent if and only if the hyperplanes intersect. This graph need not not locally finite though. – Igor Belegradek Apr 5 '10 at 0:37
• @damiano: complex hyperplanes have codimension $2$, so I do not see why connectedness comes for free. In truth I have thought more of the case when $\mathbb C^n$ is replaced with the unit ball in $\mathbb C^n$ with the complex hyperbolic metric, and in this case I have tons of examples of arrangements whose correspondning graphs aren't connected. – Igor Belegradek Apr 5 '10 at 1:00
• @damiano: actually you are right, this is what happens in $\mathbb C^n$, but things become different once we only pay attentions to intersections inside the unit ball, so in my comments above substitute $\mathbb C^n$ by the unit ball in $\mathbb C^n$ with the complex hyperbolic metric. – Igor Belegradek Apr 5 '10 at 1:19