Jozef Skokan, Separating the edges of a graph by a linear number of paths

Recently, Letzter proved that any graph of order n contains a collection P of $O(n{\log }^{\ast }n)$ paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f. We improve this upper bound to 19n, thus answering a question of Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhar and by Falgas-Ravry, Kittipassorn, Korandi, Letzter, and Narayanan.

Our proof is elementary and self-contained.