Séminaire Lotharingien de Combinatoire, 95B.101 (2026), 12 pp.
Olivier Bernardi and Jonathan J. Fang
Subgraphs Vs Orientations: Infinite Families of Equidistributions
Abstract.
A classical enumerative result states that, given a graph G and
a vertex u, the number of connected subgraphs of G is equal
to the number of orientations of G such that every vertex can
reach u by a directed path.
We show that this result is an instance of a much broader set of
enumerative identities between subgraphs and orientations
corresponding to various connectivity constraints. Namely, given two
sets of pairs of vertices A =
{(ui,vi), i ∈ [k]} and
B =
{(u'i,v'i),
i ∈ [ℓ]}, we consider the orientations α of G
such that adding the elements of A and B as additional
directed edges to α gives an orientation α' in
which vi cannot reach ui for all
i ∈ [k], but v'i can reach
u'i for all i ∈ [ℓ].
We show that this set of orientations is equinumerous to a set of
subgraphs satisfying the "same" connectivity constraints defined in
terms of A and B.
We also extend our results to the enumeration of equivalence classes of orientations satisfying such connectivity constraints. Precisely, we consider the equivalence classes under cycle reversal, cocycle reversal, or cycle-cocycle reversal. We show that the equivalences classes are equinumerous to some sets of subgraphs defined by connectivity and acyclicity constraints.
Received: November 15, 2025.
Accepted: February 15, 2026.
Final version: April 1, 2026.
The following versions are available: