Estimate size of graph by taking random walks 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?
 A: Unless you use some exhaustive criterion for stopping, such as Anton Petrunin's suggestion
of deleting vertices while maintaining connectivity and not stopping until all vertices are gone,
I do not see what class of graphs you hope will yield to such a process.  The example
below highlights my pessimism.
Take a graph G you wish to reveal.  I will pick a large positive integer k.  Pick your v_0.
I will construct k copies of G, and pick random pairs of vertices to use to add a single
edge between two copies.  I will attach my connected construct to your copy at a single
vertex, perhaps even at v_0.  I do not see how you will determine k, much less the size
of either G or my construct, without visiting all the vertices.
I think you will need something like knowing G has a nontrivial automorphism group as
well as what that group is, and use that with your locally connected information, to say
much about G.
A: Giving appropriate meaning to "generating $G$", here is one thing that could give some information: start from $v_0$ and walk until the walk has come back $k$ times to $v_0$; or possibly, instead, walk for a deterministic time $N$ and count how many times the walk visits $v_0$ during this time. This gives you, as $k$ or $N$ goes to infinity, enough information on the distribution of the return times to in particular deduce the size of the graph.
Admittedly the time needed for the algorithm will be quite a bit larger than the number of vertices. But OTOH, maybe $G$ is given implicitly as the set of states of some process, with edges given by transitions of that process, in such a way that storing the current state is (very) cheap and running the walk is easy. So, it can work with $o(n)$ memory requirement if not $o(n)$ time...
Here is a nice paper going into exactly what kind of info can on $G$ be reconstructed that way: Waiting for a bat to fly by (in polynomial time).
