  We prove that in any $n$-vertex complete graph there is a collection
$\mathcal{P}$ of $(1 + o(1))n$ paths that strongly separates any pair of
distinct edges $e, f$, meaning that there is a path in $\mathcal{P}$ which
contains $e$ but not $f$. Furthermore, for certain classes of $n$-vertex
$\alpha n$-regular graphs we find a collection of $(\sqrt{3 \alpha + 1} - 1 +
o(1))n$ paths that strongly separates any pair of edges. Both results are
best-possible up to the $o(1)$ term.
