Completing the Boundary Case of the Mahmoodian-Mirzakhani Conjecture and 117 New Computational 5-Cycle Decompositions of Complete Tripartite Graphs

Abstract

Let $K_{r,s,t}$, with $r\le s\le t$, denote the complete tripartite graph whose partite sets have sizes $r,s,t$. Mahmoodian and Mirzakhani gave three necessary conditions for $K_{r,s,t}$ to admit a decomposition into 5-cycles and conjectured that these conditions are sufficient. One of the conditions is $t\le 4rs/(r+s)$. We prove the conjecture for every odd triple on the extremal boundary $t = 4rs/(r+s)$. The proof is constructive. After reducing an arbitrary odd boundary triple to $(r,s,t)=(hga,hgb,hab)$, $a+b=4g$, we give an explicit cyclic decomposition of $K_{ga,gb,ab}$ and use the Mahmoodian and Mirzakhani scaling theorem to supply the common factor $h$. Together with the previously known all-even result, this settles the conjecture for every triple satisfying the boundary condition with equality. We also report explicit computer-generated $C_5$-decompositions for 117 odd triples satisfying the necessary conditions, 116 of which are strict-interior cases. To the best of our knowledge, all 117 cases were previously unresolved: no decomposition for any of them had been reported, and none of the 117 triples is covered by earlier existence results, constructions, or their recursive consequences. Moreover, these 117 certificates together with the boundary construction settle every previously unresolved triple satisfying the necessary conditions with fewer than $4400$ edges. Each computation is supplied as a machine-readable cycle-list certificate and can be checked independently by a short Python verifier. We also give a complete human-readable edge-label-matrix certificate for $K_{9,19,23}$.

Disclosure

“doi.org/10.5281/zenodo.21882725. The Zenodo record is the archival source for the certificates used in Proposition 5.1. Acknowledgment Sharareh Alipour kindly reviewed an earlier draft of this paper. Disclosure GPT-5.6 Sol (OpenAI) and Claude Opus 5 (Anthropic) were used in the development of this work to assist with proof development and verification, computer code and computations, and drafting and restructuring portions of the manuscript. The author reviewed and independently ver”

PDF page 10

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:21:10.249163Z

Structural counts