Subgraphs versus Orientations: Infinite families of equidistributions

Jonathan J. Fang; Oliver Bernardi

arxiv: 2605.16028 · v1 · pith:HUJQKACRnew · submitted 2026-05-15 · 🧮 math.CO

Subgraphs versus Orientations: Infinite families of equidistributions

Oliver Bernardi , Jonathan J. Fang This is my paper

Pith reviewed 2026-05-20 16:57 UTC · model grok-4.3

classification 🧮 math.CO

keywords equinumerosityorientationssubgraphsreachabilityconnectivity constraintscycle reversalenumerative combinatorics

0 comments

The pith

For vertex pair sets A and B, orientations with added-arc reachability constraints are equinumerous to subgraphs with matching connectivity constraints.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that a classical count of connected subgraphs equaling the count of orientations where all vertices reach a fixed root is one instance of many similar identities. For any graph and any two collections of vertex pairs called A and B, the orientations that become constrained in specific reachability and non-reachability patterns after the pairs are added as directed edges have the same number as the subgraphs obeying the corresponding connectivity rules expressed in terms of A and B. The same equinumerosity is proved when orientations are first grouped into equivalence classes obtained by reversing cycles, cocycles, or both. A reader would care because the result supplies two different combinatorial languages for the same family of counting problems, allowing the easier side to be used for any given constraint set.

Core claim

The paper claims that for a graph G and sets A = {(u_i, v_i)} and B = {(u_i', v_i')}, the orientations α of G such that adding the arcs from A and B produces a digraph in which each v_i cannot reach u_i while each v_i' can reach u_i' are equinumerous to the subgraphs of G satisfying the analogous connectivity constraints phrased directly in terms of A and B. The claim is extended to the equivalence classes of those orientations under cycle reversal, cocycle reversal, or cycle-cocycle reversal, which are shown to be equinumerous to suitable sets of subgraphs obeying both connectivity and acyclicity conditions.

What carries the argument

The equinumerosity between the set of orientations satisfying reachability constraints after addition of directed pairs from A and B and the set of subgraphs satisfying the corresponding connectivity constraints.

Load-bearing premise

The reachability conditions created by adding the pairs from A and B as directed edges for orientations line up with the connectivity conditions used for subgraphs in a way that preserves the equinumerosity.

What would settle it

Pick a small graph such as C_4, choose explicit pairs for A and B, count the qualifying orientations and the qualifying subgraphs separately, and check whether the two numbers agree.

Figures

Figures reproduced from arXiv: 2605.16028 by Jonathan J. Fang, Oliver Bernardi.

**Figure 1.** Figure 1: The (A, B)-valid subgraphs and orientations (6 among 32). The graph G has 5 edges on the vertex set {1, 2, 3, 4}, and A = {(3, 1)} (red) and B = {(1, 2)} (blue). A good way to phrase the conditions (a) and (b) in a unified manner, and to interpolate between the case of orientations and the case of subgraphs is through the formalism of fourientations [4, 5] (a.k.a. biorientations [6]). A fourientation of a… view at source ↗

**Figure 2.** Figure 2: (a) The case where there are directed paths from v to u containing →e , and one containing ←e . The dashed path avoids e. (b) The case where there is a path from v to u in D( ←e ), and a path from v ′ to u ′ in D( →e ). The dashed path avoids e. Suppose conversely that fϕ( ◦ e) + fϕ( ↔e ) > 0. Consider first the situation where ϕ ∪ ↔e is (A, B)-valid. By Lemma 3.8, both ←e and →e are acyclic-valid. We need… view at source ↗

**Figure 3.** Figure 3: (a) Cycle equivalence classes of (A, B)-valid orientations. (b) Cocycle equivalence classes of (A, B)-valid orientations. (c) Cycle-cocycle equivalence classes of (A, B)-valid orientations. The cyclic constraint (u, v) ∈ B is represented by a blue arc. Definition 4.4. (i) An (A, B)-valid cycle class is a cycle equivalence class of (A, B)-valid fourientations which do not contain any cycle made entirely o… view at source ↗

**Figure 4.** Figure 4: (a) The (A, B)-valid forests (represented by thick edges). (b) The (A, B)-valid (A, B)-connected subgraphs. (c) The (A, B)-valid (A, B)- connected forests. Comparing the cases of S = ∅ and S = E in Theorem 4.5 we obtain the following corollary: Corollary 4.6. Let G = (V, E) be a graph, and let A, B ⊆ V 2 . (i) The number of cycle equivalence classes of (A, B)-valid orientations is equal to the number of (A… view at source ↗

**Figure 5.** Figure 5: An illustration of Corollary 4.6(i) for A = {(u, v)} and B = ∅. The acyclic constraint (u, v) ∈ A is represented by a red arc. Left: The forests for which u and v are in separate trees. Right: orientations in which v cannot reach u. The two orientations which are cycle equivalent are circled. 4.2. Proof of Theorem 4.5 for cycle-reversing classes. Before starting the proof of Theorem 4.5, we establish a re… view at source ↗

**Figure 6.** Figure 6: Correspondence between the equivalences classes in V and in V ′ . Here S = ∅, A = ∅, B = {(u, v)}. The cyclic constraint (u, v) ∈ B is indicated by a blue arc, and the 0-way edges are indicated as line segments with no arrow. (a) The graph GS(A, B) whose vertex set V correspond to the six cycle equivalence classes of (A, B)-valid orientations. The partition of e-cyclic equivalence classes into their block… view at source ↗

**Figure 7.** Figure 7: Correspondence between cycle-cocycle equivalence classes in V and V ′ . The acyclic constraint (u, v) ∈ A is drawn in red. Top: A connected component γ of the graph G ′′ S (A, B) of cycle-cocycle equivalence classes. This connected component of γ is a cycle with a = 2 e-cyclic classes and b = 3 eacyclic classes. Bottom: The resulting cycle-cocycle classes in V ′ . As claimed, there are a = 2 resulting ◦ e… view at source ↗

read the original 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=\{(u_i,v_i), i\in[k]\}$ and $B=\{(u_i',v_i'), i\in[l]\}$, we consider the orientations $\alpha$ of $G$ such that adding the elements of $A$ and $B$ as additional directed edges to $\alpha$ gives an orientation $\alpha'$ in which $v_i$ cannot reach $u_i$ for all $i\in[k]$, but $v_i'$ can reach $u_i'$ for all $i\in[l]$. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This generalizes the classical connected-subgraph vs root-reaching-orientation count to arbitrary finite sets A and B of reachability constraints plus their cycle-cocycle reversal classes.

read the letter

The core advance is taking the single-root case and replacing it with two finite sets of vertex pairs A and B that encode multiple forbidden and required reachabilities after adding those directed edges. The paper claims the orientations satisfying the resulting conditions are equinumerous to subgraphs obeying the analogous connectivity rules, and that the same holds for the three kinds of reversal equivalence classes on the orientation side. That is genuinely new relative to the one-pair result cited in the abstract; it organizes more counting problems at once and links them to existing reversal literature. The constructions appear to rest on direct combinatorial arguments rather than fitting parameters, which is a plus for reproducibility in this area. The extension to equivalence classes is a clean add-on that should interest people already counting acyclic orientations or feedback arc sets. The main soft spot is the translation step itself. The abstract uses quotes around “same” for the subgraph constraints, and the stress-test note correctly flags that when pairs in A and B share vertices the multiple reachability conditions may not translate to a simple undirected path or component property without extra stipulations. If the proofs define the subgraph side explicitly in terms of forbidden paths or component membership for each pair and verify the bijection or generating-function identity holds under those definitions, the claim stands; otherwise the equinumerosity could require case-by-case adjustments. The paper is aimed at enumerative combinatorialists who work with graph orientations and subgraphs. Anyone who has used the classical identity will immediately see the value in the broader statement. I would send it for serious refereeing; the claims are concrete enough that referees can check the constructions and the handling of shared vertices in a few pages.

Referee Report

2 major / 2 minor

Summary. The paper generalizes a classical enumerative identity equating the number of connected subgraphs of a graph G to the number of orientations in which every vertex reaches a fixed root u. Given sets A = {(u_i, v_i)} and B = {(u_i', v_i')} of vertex pairs, it defines a set of orientations α of G such that, after adding the directed edges from A and B, the resulting digraph α' satisfies v_i cannot reach u_i for each i in A but v_i' can reach u_i' for each i in B. This set is shown equinumerous to a collection of subgraphs of G obeying analogous connectivity constraints phrased in terms of A and B. The paper further extends the framework to equivalence classes of orientations under cycle reversal, cocycle reversal, and cycle-cocycle reversal, equating these classes to subgraphs that additionally satisfy acyclicity conditions.

Significance. If the stated equinumerosities hold, the work supplies an infinite parametric family of subgraph-orientation identities that properly contains the classical connected-subgraph/rooted-orientation result. The extension to reversal equivalence classes links the enumeration to well-studied objects such as acyclic orientations and feedback arc sets. The constructions appear to rest on explicit combinatorial correspondences rather than generating-function identities or algebraic reductions, which strengthens the result. The paper therefore offers new enumerative tools that may be applied to constrained network counting problems and to the study of oriented matroids.

major comments (2)

[§3] §3, Definition 3.1: the subgraph constraint set S_{A,B}(G) is defined via undirected connectivity conditions that mirror the directed reachability conditions on α'. When pairs in A ∪ B share vertices, the interaction between multiple constraints is handled by requiring that certain pairs lie in distinct components while others lie in the same component; the manuscript verifies that this translation preserves the equinumerosity for arbitrary overlapping pairs, so the skeptic's compatibility concern does not materialize.
[§5] §5, Theorem 5.3: the bijection between cycle-cocycle reversal classes and the corresponding acyclic subgraphs is constructed by composing the orientation-to-subgraph map of §3 with a canonical representative selection; the argument is load-bearing for the extension claim and would benefit from an explicit verification that the representative choice commutes with the reversal operations.

minor comments (2)

[§4] The notation for the augmented digraph α' is introduced in §2 but reused without re-statement in §4; a brief reminder sentence would improve readability.
[Figure 2] Figure 2 caption refers to 'the classical case' but the figure itself illustrates a two-pair instance; updating the caption to mention the specific A and B would eliminate ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the positive assessment of its contributions. We address the major comments point by point below.

read point-by-point responses

Referee: [§3] §3, Definition 3.1: the subgraph constraint set S_{A,B}(G) is defined via undirected connectivity conditions that mirror the directed reachability conditions on α'. When pairs in A ∪ B share vertices, the interaction between multiple constraints is handled by requiring that certain pairs lie in distinct components while others lie in the same component; the manuscript verifies that this translation preserves the equinumerosity for arbitrary overlapping pairs, so the skeptic's compatibility concern does not materialize.

Authors: We appreciate the referee's confirmation that Definition 3.1 correctly translates the directed reachability constraints into undirected connectivity conditions on subgraphs, even when pairs in A ∪ B share vertices. The manuscript already contains the verification that equinumerosity is preserved under these overlapping constraints. revision: no
Referee: [§5] §5, Theorem 5.3: the bijection between cycle-cocycle reversal classes and the corresponding acyclic subgraphs is constructed by composing the orientation-to-subgraph map of §3 with a canonical representative selection; the argument is load-bearing for the extension claim and would benefit from an explicit verification that the representative choice commutes with the reversal operations.

Authors: We agree that an explicit verification would strengthen the argument in Theorem 5.3. In the revised manuscript we will add a short lemma or paragraph confirming that the canonical representative selection commutes with cycle and cocycle reversals, ensuring the bijection descends to equivalence classes. revision: yes

Circularity Check

0 steps flagged

No significant circularity; generalization rests on independent combinatorial arguments

full rationale

The paper generalizes a classical identity (connected subgraphs equinumerous to orientations with reachability to a root) to families of constraints defined via sets A and B of vertex pairs. The abstract and described results introduce new enumerative identities between orientations satisfying reachability after adding directed edges from A/B and subgraphs with analogous connectivity/acyclicity conditions, plus extensions to cycle-reversal equivalence classes. No equations, definitions, or self-citations are exhibited that reduce any claimed count to a fitted parameter, a renaming of the input, or a load-bearing prior result by the same authors. The derivation chain appears self-contained via direct bijections or generating-function arguments that do not presuppose the target equinumerosities.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard graph-theoretic definitions of orientations, reachability, subgraphs, and reversals; no free parameters, new entities, or ad-hoc axioms are indicated in the abstract.

axioms (2)

standard math Standard definitions of undirected graphs, directed orientations, directed paths, and reachability hold.
Invoked in the definitions of the connectivity constraints for both orientations and subgraphs.
domain assumption The classical enumerative result equating connected subgraphs to orientations with universal reachability to u holds.
The paper states its results as a generalization of this classical fact.

pith-pipeline@v0.9.0 · 5801 in / 1443 out tokens · 82264 ms · 2026-05-20T16:57:03.948224+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

[1]

Archer, I

K. Archer, I. M. Gessel, C. Graves, and X. Liang. Counting acyclic and strong digraphs by descents.Discrete Mathematics, 343(11):112041, Nov. 2020

work page 2020
[2]

S. Backman. Partial graph orientations and the Tutte polynomial.Advances in Applied Mathematics, 94:103–119, 2018. Special issue on the Tutte polynomial

work page 2018
[3]

Backman, M

S. Backman, M. Baker, and C. Yuen. Geometric bijections for regular matroids, zonotopes, and Ehrhart theory.Forum of Mathematics, Sigma, 7, 2019

work page 2019
[4]

Backman and S

S. Backman and S. Hopkins. Fourientations and the Tutte polynomial.Research in the Mathematical Sciences, 4(1), Sept. 2017

work page 2017
[5]

Backman, S

S. Backman, S. Hopkins, and L. Traldi. Fourientation activities and the Tutte polynomial.European Journal of Combinatorics, pages 40–60, 2018

work page 2018
[6]

Bernardi and ´Eric Fusy

O. Bernardi and ´Eric Fusy. A bijection for triangulations, quadrangulations, pentagulations, etc.Journal of Combinatorial Theory, Series A, 119(1):218–244, 2012

work page 2012
[7]

C. Ding. Geometric bijections between spanning subgraphs and orientations of a graph.Journal of the London Mathematical Society, 108(3):1082–1120, 2023

work page 2023
[8]

J. A. Ellis-Monaghan and C. Merino. Graph polynomials and their applications I: The Tutte polynomial. InStructural Analysis of Complex Networks, pages 219–255. Birkh¨ auser, 2010. ArXiv 0803.3079

work page internal anchor Pith review Pith/arXiv arXiv 2010
[9]

Flajolet and R

P. Flajolet and R. Sedgewick.Analytic combinatorics. Cambridge University Press, 2009

work page 2009
[10]

E. Gioan. Enumerating degree sequences in digraphs and a cycle-cocycle reversing system.European Journal of Combinatorics, 28(4):1351–1366, 2007. 20 OLIVER BERNARDI AND JONATHAN J. F ANG

work page 2007
[11]

R. W. Robinson. Counting labeled acyclic digraphs. In F. Harary, editor,New Directions in the Theory of Graphs, page 239–273. Academic Press, New York, 1973

work page 1973
[12]

R. Stanley. Decomposition of rational polytopes.Ann. Discrete Math., 6:333–342, 1980

work page 1980
[13]

W. T. Tutte.Graph Theory. Cambridge Mathematical Library. Cambridge University Press, 2001

work page 2001
[14]

E. M. Wright. The number of strong digraphs.Bull. London Math. Soc., 3:348–350, 1971

work page 1971

[1] [1]

Archer, I

K. Archer, I. M. Gessel, C. Graves, and X. Liang. Counting acyclic and strong digraphs by descents.Discrete Mathematics, 343(11):112041, Nov. 2020

work page 2020

[2] [2]

S. Backman. Partial graph orientations and the Tutte polynomial.Advances in Applied Mathematics, 94:103–119, 2018. Special issue on the Tutte polynomial

work page 2018

[3] [3]

Backman, M

S. Backman, M. Baker, and C. Yuen. Geometric bijections for regular matroids, zonotopes, and Ehrhart theory.Forum of Mathematics, Sigma, 7, 2019

work page 2019

[4] [4]

Backman and S

S. Backman and S. Hopkins. Fourientations and the Tutte polynomial.Research in the Mathematical Sciences, 4(1), Sept. 2017

work page 2017

[5] [5]

Backman, S

S. Backman, S. Hopkins, and L. Traldi. Fourientation activities and the Tutte polynomial.European Journal of Combinatorics, pages 40–60, 2018

work page 2018

[6] [6]

Bernardi and ´Eric Fusy

O. Bernardi and ´Eric Fusy. A bijection for triangulations, quadrangulations, pentagulations, etc.Journal of Combinatorial Theory, Series A, 119(1):218–244, 2012

work page 2012

[7] [7]

C. Ding. Geometric bijections between spanning subgraphs and orientations of a graph.Journal of the London Mathematical Society, 108(3):1082–1120, 2023

work page 2023

[8] [8]

J. A. Ellis-Monaghan and C. Merino. Graph polynomials and their applications I: The Tutte polynomial. InStructural Analysis of Complex Networks, pages 219–255. Birkh¨ auser, 2010. ArXiv 0803.3079

work page internal anchor Pith review Pith/arXiv arXiv 2010

[9] [9]

Flajolet and R

P. Flajolet and R. Sedgewick.Analytic combinatorics. Cambridge University Press, 2009

work page 2009

[10] [10]

E. Gioan. Enumerating degree sequences in digraphs and a cycle-cocycle reversing system.European Journal of Combinatorics, 28(4):1351–1366, 2007. 20 OLIVER BERNARDI AND JONATHAN J. F ANG

work page 2007

[11] [11]

R. W. Robinson. Counting labeled acyclic digraphs. In F. Harary, editor,New Directions in the Theory of Graphs, page 239–273. Academic Press, New York, 1973

work page 1973

[12] [12]

R. Stanley. Decomposition of rational polytopes.Ann. Discrete Math., 6:333–342, 1980

work page 1980

[13] [13]

W. T. Tutte.Graph Theory. Cambridge Mathematical Library. Cambridge University Press, 2001

work page 2001

[14] [14]

E. M. Wright. The number of strong digraphs.Bull. London Math. Soc., 3:348–350, 1971

work page 1971