Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size

We propose a randomized algorithm with query access that given a graph G with arboricity α, and average degree d, makes O (α²d) Degree and O (1²) Random Edge queries to obtain an estimate d satisfying d (1) d. This improves the O, ₍ (n{d}) query algorithm of Beretta et al. , SODA 2026 that has access to Degree, Neighbour, and Random Edge queries. Our algorithm does not require any graph parameter as input, not even the size of the vertex set, and attains both simplicity and practicality through a new estimation technique. We complement our upper bounds with a lower bound that shows for all valid n, d, and α, any algorithm that has access to Degree, Neighbour, and Random Edge queries, must make at least Ω ( (d, αd) ) queries to obtain a (1) -multiplicative estimate of d, even with the knowledge of n and α. We also show that even with Pair and FullNbr queries, an algorithm must make Ω ( (d, αd) ) queries to obtain a (1) -multiplicative estimate of d. Our work addresses both the questions raised by the work of Beretta et al. , SODA 2026.