Graphs with many strong orientations

Sinan Aksoy, Paul Horn

We establish mild conditions under which a possibly irregular, sparse graph $G$ has "many" strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direct…