# Degree of girraphs

A girraph is an infinite, regular, vertex-transitive graph, on which a random walk is recurrent.

The random walk on the square grid returns to the origin with probability 1, and for the cubic grid about 34%. The square grid has degree 4, and the cubic grid has degree 6.

-What is the highest degree a girraph can have?

Is there any easy way to check if a graph is a girraph?

-
I see you accepted my answer. Thanks for the appreciation, but in my opinion this is much too soon after you asked the question (31 minutes). Other answers might come, so why the rush... –  Did Nov 8 '11 at 5:50
Ok, I have another question too, is it possible to have a graph where the expected number of returns to the origin is >1, but the probability to return is <1 ? –  harry_b Nov 8 '11 at 6:58
Yes. The expected number of returns is p/(1-p) with p the probability to return. –  Did Nov 8 '11 at 7:08

The degree may be as large as one wants. Consider any nonempty finite set $S$ and $G=\mathbb Z\times S$ with edges between $(x,s)$ and $(y,t)$ in $G$ if and only if $|x-y|=1$. The degree of every vertex of $G$ is twice the size of $S$ and $G$ is regular and vertex transitive. To see that $G$ is recurrent, note that almost surely every $x$ in $\mathbb Z$ is visited infinitely often because the induced random walk on $\mathbb Z$ is recurrent. Furthermore, the sequence $(s_n)_n$ of the second coordinates at the times when the walk is at $x$ is i.i.d. in $S$ hence almost surely $s_n=s$ for infinitely many integers $n$, for any given $s$ in $S$. This proves that every $(x,s)$ in $G$ is visited infinitely often.