A separating path system is a collection of paths in a simple graph that distinguishes its edges by their membership in the paths. There are weak and strong versions of this condition (Bonamy et al. 2023).
A weakly separating path system requires that, for every pair of distinct edges 
and 
, some path contains exactly
one of them. A strongly separating path system requires both a path
containing 
but not 
and a path containing 
but not 
. The size of either system is the number of paths
in the collection. Every strongly separating path system is weakly separating, but
the converse need not hold.
For example, in a triangle graph with edges 
, 
, and 
, the two paths with edge
sets 
and 
form a weakly separating path system. They do not form a strongly separating path
system, since neither contains 
without 
. The three single-edge paths form a strongly separating path system.
Bonamy et al. (2023) proved that every simple graph on 
vertices admits a strongly separating path system with
at most 
paths.
