2026/08/02 by Jitendra Prajapati
Mathematics · Computer Science · #math.CO #cs.DM #msc:05C05 #msc:05C40 #msc:68R10 #acm:05C05 #acm:05C40 #acm:68R10
5 pages. Certificate and solver-free verifier available at https://github.com/infinityscroll/f4-dualcube-cist
arxiv created 2026/08/02 · arxiv updated 2026/08/04
Lalou, Mbarek, Skender and Togni (arXiv:2607.25917) proved that the n-dimensional dual-cube Fn admits two completely independent spanning trees for every n≥ 5, observed that none exist for n≤ 3, and identified F4 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: Fn admits two completely independent spanning trees if and only if n≥ 4. The internal-vertex sets of the two trees are the level sets of a single ten-term cubic polynomial over \mathbbF2 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 F4 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.