Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:

- We take a random walk starting at $v_0$.
- Along the way, we can collect local information such as the degrees of vertices visited. We can also make local modifications to $G$, e.g. by deleting vertices and edges adjacent to where we've been.
- At the end of the walk (triggered by some event such as having no remaining moves), we use the collected information to compute an unbiased estimator for the number of vertices in $G$.

Specifically, I'm interested in such methods that may be feasible in **some** cases (all would be too much to ask) where generating $G$ in its entirety is not feasible.

The inspiration for this question is a paper of Donald Knuth that does precisely the above for trees. Applying Knuth's method to a more general graph produces an estimate of the number of possible walks, not the number of vertices.

Ideas?

1more comment