Bijection Between Eulerian Orientations and Bicolored Trees

Definitions and mathematical statement

An orientation of a finite graph assigns a direction to each edge. It is Eulerian if, at every vertex $v$, the indegree and outdegree agree: \[ \deg^{-}(v)=\deg^{+}(v). \] A planar embedding embeds a graph in the sphere without edge crossings. A tree is a connected acyclic graph. A bicolouring assigns one of two colours to each vertex; whether adjacent vertices must receive different colours is an additional condition that the supplied record does not specify.

The supplied problem asks for an explicit bijection \[ \Phi:\mathcal E\longrightarrow\mathcal T, \] where $\mathcal E$ is the intended class of rooted planar Eulerian orientations and $\mathcal T$ is the corresponding class of bicoloured trees. A bijective proof must specify the construction and its inverse and prove that they are mutually inverse.

Unresolved formulation. The supplied record does not define the corresponding tree class. It also does not specify the rooting and equivalence conventions for the planar objects, whether loops and multiple edges are allowed, or any restrictions on the underlying graphs. For the trees, rooting, planar order, colouring constraints, and any additional structure are unspecified. If the intended equinumerosity is coefficientwise, the size parameters and their correspondence must also be supplied: for the intended graded classes $\mathcal E_n$ and $\mathcal T_n$, the requested construction would give bijections $\Phi_n:\mathcal E_n\to\mathcal T_n$ for every admissible index $n$. Neither those classes nor that index range can be recovered from this record. Thus the displayed target expresses the requested construction, but a fully specified standalone mathematical problem requires the missing class definitions and conventions.

Short English statement

Construct an explicit bijection between the intended rooted planar Eulerian orientations and their corresponding bicoloured trees. The supplied record leaves the tree family, several map conventions, and the counting parameters undefined, so the exact bijection problem remains underdetermined. This is a statement-only draft requiring human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003816$, title Bijection Between Eulerian Orientations and Bicolored Trees, exact source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. No individual proposer is supplied; the proposed year is recorded as 2018.
• Supplied source citation: Enumerative Combinatorics (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/23, pp. 1381--1464. Original OWR report: https://doi.org/10.4171/owr/2018/23. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source labelled "refined Eulerian-orientation enumeration": https://arxiv.org/abs/2503.15046.
• Literature assessment dated 2026-08-21: supplied dated curation, not independently verified. It labels the problem open and states that generating functions for planar Eulerian orientations are known, that the report explicitly leaves open a bijective proof with the corresponding bicoloured trees, and that later refined enumerations do not supply that bijection. The background identifies this assessment as dated literature triage derived from the supplied OWR curation and calls for independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified, explaining that mathematical content was preserved while notation, typography, and sentence structure were repaired for publication. This is supplied editorial metadata, not independent mathematical verification of this draft.