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.