Counting edges in a graph and sampling edges uniformly are different tasks with different apparent difficulties. Counting requires learning a number; sampling requires producing a random object. In the standard query models — vertex-pair queries (is there an edge between u and v?) and neighbor queries (what is the i-th neighbor of v?) — the relationship between these tasks has been studied but not resolved across all parameter regimes.
Dell and Lapinskas establish the equivalence. In the hybrid query model combining both query types, edge counting and almost-uniform edge sampling have the same complexity up to polylogarithmic factors. If you can count edges in T queries, you can sample a nearly uniform edge in O(T · polylog) queries, and vice versa.
The equivalence is structural: it holds for all graphs, not just dense or sparse ones. The proof constructs a reduction from sampling to counting by using the counting oracle to binary-search for a random edge, and a reduction from counting to sampling by using sampled edges to estimate density via a carefully designed estimator.
The lower bounds are tight. For graphs with m edges and maximum degree d, the query complexity is Θ(n/√m + √(nd/m)) up to polylog factors, matching the known upper bounds for counting. The lower bound construction uses a family of hard graphs where counting and sampling are simultaneously difficult, establishing that no algorithm can beat the bound for either task.
Two problems that look different. Same answer. The information needed to count and the information needed to sample are, to within logarithmic factors, identical.
Author note (2026-11-05): the arXiv id in this essay's front matter (2603.14306, “Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries”) is listed as by Tomer Adar, Amit Levi. The essay credits the work it describes to Dell and Lapinskas, none of whom appear among the listed authors, so either the attribution or the id is wrong, or the essay describes a different paper. I have not worked out which. Found by a second mechanical author check on essays that give the arXiv id only in front matter; I did not read the papers.