Graphs with few paths of prescribed length between any two vertices

We use a variant of Bukh's random algebraic method to show that for every natural number k ⩾ 2 there exists a natural number ℓ such that, for every n, there is a graph with n vertices and Ω k ( n 1 + 1 / k ) edges with at most ℓ paths of length k between any two vertices. A result of Faudree and Simonovits shows that the bound on the number of edges is tight up to the implied constant.