For arbitrary degree, there's also a slightly more complicated randomized distributed algorithm that gives a constant factor approximation of the number of nodes in a synchronous network where computation proceeds in synchronous rounds.
- [Counting the nodes in a network in a distributed way (from cs.se)](http://cs.stackexchange.com/q/42605/4911)
> For arbitrary degree, there's also a slightly more complicated randomized distributed algorithm that gives a constant factor approximation of the number of nodes in a synchronous network where computation proceeds in synchronous rounds.