Q. Is there a master theorem that can be used to determine whether or not
a simple random walk (choose a random neighboring vertex as the next step)
on a given infinite graph
leads to recurrence (almost surely returns to the start vertex)?
Added. Let's restrict the graphs to be locally finite, in the sense
that every vertex has finite degree.
For example, the infinite path is recurrent, as it is equivalent to $\mathbb{Z}^1$, but I believe the infinite binary tree is not recurrent,
i.e., it is transient. I am seeking structural properties of a graph that
determines its recurrence/transience behavior.
Best Answer
In my opinion, the closest to a "master theorem" is the criterion due to Terry Lyons, according to which a reversible Markov chain on a countable state space (in particular, the simple random walk on a locally finite graph) is transient if and only if there exists a flow of finite energy on the state space.
PS Contrary to the opinion appearing in the comments, in this criterion no conditions other than reversibility (e.g., uniform bounds on vertex degrees) are imposed. Actually, there are quite instructive examples of reversible random walks with unbounded weights (for instance, any nearest neighbour random walk on a tree).
Theorem from Terry Lyons paper (added by J.O'Rourke).