Separating Path Systems in Complete Graphs

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.