The bipartite analogue of a classical spanning tree enumeration formula, Boolean functions, and their applications to counting odd spanning trees

Jun Ge, Yamin Yu · 2026

Read The bipartite analogue of a classical spanning tree enumeration formula, Boolean functions, and their applications to counting odd spanning trees by Jun Ge, Yamin Yu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-13750.txt.

Description

An odd spanning tree of a graph is a spanning tree in which every vertex has odd degree, a concept recently defined by Zheng and Wu. Feng, Chen, and Wu counted odd spanning trees in complete graphs using Prufer codes and exponential generating functions, in the spirit of Cayley's formula. This note gives a simple proof through a classical spanning tree enumeration formula and Boolean functions, and generalizes the result to complete bipartite graphs.

The proof's simplicity is its contribution: a classical enumeration formula plus Boolean function reasoning recovers and extends a recent counting result without heavy machinery. By moving from complete graphs to complete bipartite graphs, the note widens the class of graphs whose odd spanning trees are now counted. Jun Ge leads the work with one co-author.

Catalog record

CREATORJun Ge, Yamin Yu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-13750

Browse the full library · About the Tower of Babel