MathAudit

Paper metadata

Original submission
May 15, 2026
Claimed MSC
arXiv categories
math.CO

Abstract

A classical enumerative result states that, given a graph GG and a vertex uu, the number of connected subgraphs of GG is equal to the number of orientations of GG such that every vertex can reach uu 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]}A=\{(u_i,v_i), i\in[k]\} and B={(ui′,vi′),i∈[l]}B=\{(u_i',v_i'), i\in[l]\}, we consider the orientations α\alpha of GG such that adding the elements of AA and BB as additional directed edges to α\alpha gives an orientation α′\alpha' in which viv_i cannot reach uiu_i for all i∈[k]i\in[k], but vi′v_i' can reach ui′u_i' for all i∈[l]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 AA and BB. 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.

Dependence graphs

Proof lineage

Subgraphs versus Orientations: Infinite families of equidistributions

Full statement-restricted recursive proof-dependence graph for arXiv:2605.16028v1. Theorem 3.1 and its main enumerative corollaries are proved locally and independently verified. The equivalence-class family in Theorem 4.5 is not correct under the literal Section 2 digraph definitions: an arc-set cocycle cannot contain a 0-way edge, while reciprocal arcs of one 2-way nonloop edge form a digraph 2-cycle. Replacing those notions by the standard underlying-edge-simple potential cocycle/cycle notions makes Definition 4.4 meaningful and verifies the intended theorem. The chosen proof chain for Fact 4.10 uses Backman's graph-specific, self-contained cut/cycle decomposition; the independently sufficient BBY and Ding routes were inspected but are excluded as alternative proofs rather than drawn as parallel mandatory parents. Flajolet–Sedgewick is the terminal book source for Corollary 3.7. Historical, terminology, comparison, and locally reproved citations are excluded. Example 3.4 additionally needs X and Y nonempty, and two informal specializations need G connected.

Open dependence graph →

AI-generated audit

Audit summary

Audited against arXiv v1

Not a correctness certificate. A green “no issues found” result may include yellow suspected typos or minor formal issues that do not affect substantive soundness. It means this audit found no unresolved substantive error under the stated criteria; it does not replace expert scrutiny or formal verification.

Current report

Detailed mathematical audit

Generated August 31, 2026
01Statements5 reported findingsSuspected incorrect statements

The solid-set invariance in Theorem 3.1 and its enumerative consequences through Corollary 3.7 are correct. The equivalence-class invariance in Theorem 4.5 is false under the paper's literal Section 2 arc-digraph definitions: a 0-way edge supplies no arc and therefore cannot belong to the cocycle that Definition 4.4 requires, while using both opposite arcs of one 2-way edge also conflicts with the intended underlying-edge cycle convention. A standard potential-cycle and potential-cut definition repairs the theorem, and exhaustive tests then pass. Example 3.4 and one introductory specialization also omit necessary qualifications.

Theorem 3.1 and Corollary 3.2No issue found

The subgraph-orientation invariance is correct

PDF pages 4 and 6-8 · theorem, local four-state identity, and corollary · arXiv:2605.16028v1

For a fixed edge, the two 1-way configurations and the two solid configurations have equal valid-state totals. Lemmas 3.8-3.9 correctly separate monotonicity from the cyclic-versus-acyclic upgrade, and the two claims cover totals zero, one, and two. Exhaustive enumeration checked every simple graph on at most three vertices and every pair of constraint sets, for 32,801 theorem instances; 68 selected loop and parallel-edge instances also passed.

Corollaries 3.6 and 3.7Correct, with a proof repair recorded below

The polynomial and generating-function identities are correct

PDF pages 5-6 · Equations (1)-(4) and their proofs · arXiv:2605.16028v1

Direct polynomial expansion agrees on both sides of Equation (1) for every simple graph on at most three vertices. Equation (4) follows because a tournament is an ordered sequence of its strong components, whereas a totally cyclic fourientation is a labelled set of its strong components. The resulting relation is equivalent to the Archer-Gessel-Graves-Liang formula.

Section 2, Definition 4.4, and Theorem 4.5Suspected false under the stated definitions; coherent after an explicit repair

The fourientation cycle and cocycle definitions do not support the stated theorem

PDF page 3 · directed cycles and cocycles of a fourientation; PDF pages 9-10 · Definition 4.4 and Theorem 4.5 · arXiv:2605.16028v1

Section 2 defines cycles and cocycles of a fourientation as those of its arc digraph. A 0-way edge has no arc, so a cocycle made entirely of 0-way edges is impossible literally. For a graph consisting of one nonloop edge with empty constraint sets, the two orientations form one cocycle-reversal class when the solid set is empty, but the 0-way and 2-way states give two surviving singleton classes when the edge is solid. Thus Theorem 4.5(ii) has counts one and two. The cycle language has the parallel ambiguity that the two opposite arcs of one 2-way edge can form a digraph 2-cycle even though the later forest interpretation must use each original edge at most once. The unique natural repair is to define potential cycles and cuts on underlying edge supports: allow a 2-way edge on a cycle without reusing it, and allow 0-way crossing edges on a cut while forbidding 2-way crossings. Under this repaired semantics, all 98,403 exhaustive cycle, cocycle, and cycle-cocycle class instances and the selected multigraph cases passed.

Example 3.4Suspected incorrect at an omitted boundary case

The existential characterization needs both vertex sets nonempty

PDF page 4 · Example 3.4 · arXiv:2605.16028v1

If XX is empty and Y=VY=V, or conversely, then B=X×YB=X\times Y is empty and every orientation or subgraph is valid, while the displayed existential reachability and component conditions are impossible for nonempty VV. Adding X≠∅X\neq\varnothing and Y≠∅Y\neq\varnothing repairs the example. With that assumption, the characterization is correct: paths can be spliced through the added arcs from XX to YY, and first-arc and last-arc truncation proves the converse.

Disconnected graphs in the introductionSuspected incorrect as stated for disconnected graphs

Connected subgraphs and spanning trees require a connectivity qualification

PDF page 3 · final paragraph of the introduction · arXiv:2605.16028v1

With empty constraint sets, the introduction says cocycle classes and cycle-cocycle classes correspond to connected subgraphs and spanning trees. For two isolated vertices there is one orientation class but neither a connected spanning subgraph nor a spanning tree. Corollary 4.6 later gives the correct formulation through component-preserving connectedness. The introductory sentence should either assume that GG is connected or say component-preserving spanning subgraphs and spanning forests.

02Proofs6 reported findingsSuspected incomplete or incorrect proofs

Theorem 3.1 has a sound self-contained proof after two forced notation repairs. The proof of Corollary 3.6 makes a false coefficient identification when a monomial contains both oriented arcs of one original edge, although the identity is correct and the omitted zero-coefficient case repairs it. Section 4 proves the intended potential-cycle and potential-cut theorem rather than the literal definitions stated in Section 2; after inserting those definitions, its contraction, reversal, outdegree, flow, and component-counting arguments are coherent, with several compressed analogies and local cross-reference defects still requiring repair.

Proof of Theorem 3.1Correct after two local notation repairs

The four-state argument closes

PDF pages 6-8 · Lemmas 3.8-3.9 and Claims 1-2 · arXiv:2605.16028v1

Adding arcs preserves every cyclic constraint and can only destroy an acyclic constraint. If a chosen orientation of the active edge is cyclic, upgrading it to 2-way preserves strong components; if it is acyclic, deleting it cannot destroy a cycle witnessing a constraint from BB. The two path-splicing claims then force equality of the two configuration sums. The opening must read S⊆ES\subseteq E, not S⊆VS\subseteq V, and the fixed object on page 6 is a fourientation of G∖eG\setminus e, not necessarily an orientation.

Proof of Corollary 3.6Suspected incorrect as written; uniquely repairable

The printed coefficient identification omits conflicting arc variables

PDF page 5 · proof of Equation (1) · arXiv:2605.16028v1

Take one edge joining vertices zero and one, let AA be empty, and put both opposite arcs in BB. The coefficient of z01z10z_{01}z_{10} is zero on each side of Equation (1), because one original edge cannot be two different 1-way arcs. The claimed valid-subgraph coefficient after deleting that edge is one, since the two adjoined arcs form a directed cycle. The proof is repaired by first observing that every monomial using both arcs of one edge has coefficient zero on both sides, and applying the deletion argument only when the chosen arcs have distinct underlying edges. The displayed polynomial identity itself passed independent exhaustive expansion.

Theorem 4.5Suspected incomplete for the stated theorem; coherent for the repaired theorem

The proof needs the missing potential-cycle and potential-cut definitions

PDF pages 8-19 · Lemma 4.2 through Lemma 4.19 and the three class counts · arXiv:2605.16028v1

The proof repeatedly treats 2-way edges as usable but fixed on an underlying cycle, and 0-way edges as usable but fixed on an underlying cut. Those are standard potential-cycle and potential-cut semantics, not the arc-digraph definition printed in Section 2. Once the missing definitions are supplied, Lemma 4.9 gives disjoint reversal supports, Lemmas 4.11, 4.14, and 4.17 bound adjacency degrees, the outdegree and cycle-flow potentials rule out monochromatic nontrivial cycles, and the block associations give the required componentwise counts. Independent enumeration found no counterexample under that repaired semantics, but computation is not a proof and cannot repair the missing definition silently.

Fact 4.10 and Lemma 4.9Correct after two symbol repairs

The disjoint decomposition input is valid

PDF pages 11-12 · Fact 4.10 and proof of Lemma 4.9 · arXiv:2605.16028v1

The symmetric difference vector of two directed cycles or cocycles is a signed zero-one vector in the corresponding cycle or cocycle lattice, hence decomposes conformally into edge-disjoint directed cycles or cocycles. The cited Backman, Backman-Baker-Yuen, and Ding sources contain the needed graph or regular-matroid statements. In the focal proof the reversal sequence is introduced as C1,…,CnC_1,\ldots,C_n but once called C1,…,CkC_1,\ldots,C_k, and the reduced orientation α′\alpha' is printed as coming from undefined ψ\psi rather than ϕ′\phi'. Both corrections are forced by the surrounding sentence.

Section 4 expositionSuspected repairable exposition gaps

Several cross-references and analogous-proof transitions need correction

PDF pages 15-19 · cocycle and cycle-cocycle cases · arXiv:2605.16028v1

The cocycle adaptation should say that Corollary 4.15 replaces Corollary 4.12 and Lemma 4.16 replaces Lemma 4.13; the printed sentence reverses both roles. The proof of Corollary 4.18 must use GS′′(A,B)\mathcal G''_S(A,B), not GS(A,B)\mathcal G_S(A,B), and the final component count must again use the double-prime graph, not GS′(A,B)\mathcal G'_S(A,B). Lemmas 4.14, 4.16, 4.17, and 4.19 are justified only by analogy. Their intended arguments do transfer after the definition repair, but writing the lifted block-association argument explicitly would close the proof at publication standard.

Local typesetting defectsSuspected typos

Three further printed slips have forced readings

PDF pages 4, 5, and 15 · Remark 3.5, proof of Corollary 3.6, and subsection 4.3 heading · arXiv:2605.16028v1

Remark 3.5 writes the two members of BB with unordered-pair braces even though B⊆V2B\subseteq V^2; they must be the ordered pairs (1,2)(1,2) and (2,3)(2,3). The proof of Corollary 3.6 cites 'Theorem 1' through the equation label, but must cite Theorem 3.1. The subsection heading says 'Proof of of'. None of these three slips changes a mathematical conclusion.

03Novelty0 reported findingsNo novelty concerns found

No non-novelty findings.

04Sources4 reported findingsNo source-use issues found

The exact official arXiv v1 PDF and source archive are frozen, and every proof-critical input and every historical attribution evaluated in this audit was checked in an exact arXiv version, an official author-hosted journal copy, or the authors' official book copy. The citations attached to Fact 4.10 support the needed disjoint cycle and cocycle decomposition; Archer-Gessel-Graves-Liang and Flajolet-Sedgewick support Corollary 3.7; and Gioan's author-hosted published article supports the historical reversal-class attributions and the rooted-connectivity specialization. Remaining citations supply standard background or contextual attribution rather than an unproved logical step used by the focal arguments audited here.

Review formExact source verified

The exact official v1 record is frozen

Official abstract, 20-page PDF, and source archive · arXiv:2605.16028v1

The official record was submitted on May 15, 2026. The PDF and TeX title use Oliver Bernardi and Jonathan J. Fang; the submission-history contact is displayed as Olivier Bernardi. The license is the arXiv nonexclusive distribution license. The report treats the PDF name as authoritative for this paper and does not infer a separate author identity from the contact spelling.

Official arXiv:2605.16028v1 ↗
Fact 4.10Applicable and sufficient

The cycle and cocycle decomposition citations support the imported fact

PDF pages 11-12 · Fact 4.10 and Lemma 4.9 · exact arXiv fallbacks 1408.3962v3, 1701.01051v3, and 2109.01930v4 · arXiv:2605.16028v1

Backman proves that differences of cut-reversal-related partial orientations decompose into edge-disjoint directed cuts and records the dual cycle statement. Backman-Baker-Yuen Lemma 4.1.1 gives conformal disjoint signed-circuit decomposition for signed zero-one vectors in a regular matroid, and Ding Lemma 2.5 states the graph cycle and cocycle versions directly. These match the focal symmetric-difference use after restricting to cuts that avoid the added constraint arcs.

Ding, exact arXiv:2109.01930v4 ↗
Corollary 3.7Applicable and sufficient

The attributed generating-function identity and standard constructions match

PDF pages 5-6 · Corollary 3.7 and proof · exact arXiv:1909.01550v3 and official Analytic Combinatorics copy · arXiv:2605.16028v1

Archer-Gessel-Graves-Liang Equation (16) is the logarithmic form equivalent to the focal exponential identity. Flajolet-Sedgewick's labelled sequence and set constructions give respectively the reciprocal and exponential generating functions used in the proof. The focal application preserves the empty and one-vertex cases.

Archer, Gessel, Graves, and Liang, exact arXiv:1909.01550v3 ↗
Gioan historical inputApplicable and sufficient

The author-hosted published article supports the attributed special cases

PDF pages 1, 3, and 10 · root-connectivity identity and reversal-class history · Gioan published pages 1355-1364 · arXiv:2605.16028v1

Gioan's exact author-hosted European Journal of Combinatorics article proves the relevant Tutte-polynomial counts: Theorem 3.4 and Proposition 4.7 with Corollary 4.8 give the rooted reachability and cocycle-class specialization, while Corollaries 4.11 and 4.13 give the cycle and cycle-cocycle class counts. Its Section 4 explicitly assumes a connected graph, which agrees with the connectivity qualification independently required for the focal introduction's spanning-tree wording.

Gioan, author-hosted European Journal of Combinatorics article ↗
Detailed audit reportFull reasoning, manuscript locations, and references.
Open report PDF ↗

Author response

Challenge an audit finding

Local workflow preview

A listed author may submit formal evidence that an audit is inaccurate. The response would be considered in a fresh AI re-evaluation; it would not edit the audit automatically.

Paper
arXiv:2605.16028v1
Authors listed
Oliver Bernardi, Jonathan J. Fang
Audit date
August 31, 2026
  1. 01Establish identityMatch an authenticated scholarly identity to this paper.
  2. 02Submit evidenceIdentify the finding and give a formal mathematical response.
  3. 03Re-evaluateA separate agent checks the response and records a disposition.
Recommended production method

Authenticate with ORCID, then require an exact arXiv match

MathAudit should accept the identity only when ORCID OAuth authenticates the claimant's iD and this exact arXiv paper appears in arXiv's public authority feed for that iD. A matching name alone is not sufficient.

ORCID OAuth and arXiv authority-record lookup are not connected in this local prototype.

Email fallback for papers without a linked ORCID

A production fallback could send a one-time link only when the submitted address matches an independently maintained author-contact allowlist for this paper. MathAudit must return the same message for every address so the form cannot reveal which contacts are on that list.

This demonstration does not send, store, or compare the address.

Structured response preview

This form remains unavailable until production identity verification succeeds. Nothing entered here is submitted.

This panel never establishes authorship in the local prototype. A production result should be described narrowly as an authenticated ORCID match or control of a separately allowlisted author-contact mailbox.