An explicit construction of two completely independent spanning trees in the four-dimensional dual-cube

Abstract

Lalou, Mbarek, Skender and Togni (arXiv:2607.25917) proved that the $n$-dimensional dual-cube $F_n$ admits two completely independent spanning trees for every $n\ge 5$, observed that none exist for $n\le 3$, and identified $F_4$ as the first unresolved case, reporting more than 700 hours of inconclusive computation. We settle this case affirmatively by an explicit construction, completing the classification: $F_n$ admits two completely independent spanning trees if and only if $n\ge 4$. The internal-vertex sets of the two trees are the level sets of a single ten-term cubic polynomial over $\mathbb{F}_2$ in the seven vertex bits, and correctness reduces to finite connectivity checks that are machine-verified by a solver-free program distributed with the certificate. In $F_4$ the two trees necessarily use 254 of the 256 edges. We also report exact infeasibility results for simpler rules of the same shape: within the search model, no affine or quadratic rule works, and ten terms is the fewest possible for a cubic rule.

Disclosure

“roll/f4-dualcube-cist. Veri- fication requires one command: python3 verify anf structure.py anf-construction.json. Acknowledgements The search programs, the certificate, and an initial draft of this note were produced with AI assistance (OpenAI Codex, with subsequent verification and preparation assisted by Claude); the author directed the work, independently re-verified the construction, and takes full responsibility for the content. A documented literature search located no ear”

PDF page 4

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T19:17:00.242643Z

Structural counts