For positive integers r≤ s≤ t, the complete tripartite graph K_r,s,t admits a decomposition into 5-cycles if and only if r equiv s equiv t pmod2, rs+rt+st equiv 0 pmod5, and t≤ frac4rsr+s; that is, there is a collection C of 5-cycles such that E(K_r,s,t) is the disjoint union of the edge sets of the cycles in C.

Mahmoodian–Mirzakhani conjecture

For positive integers $r\le s\le t$ , the complete tripartite graph $K_{r,s,t}$ admits a decomposition into $5$ -cycles if and only if $r\equiv s\equiv t\pmod{2}$ , $rs+rt+st\equiv 0\pmod{5}$ , and $t\le \frac{4rs}{r+s}$ ; that is, there is a collection $\mathcal{C}$ of $5$ -cycles such that $E(K_{r,s,t})$ is the disjoint union of the edge sets of the cycles in $\mathcal{C}$ .

Progress summary

Partially solved

A new paper proves the conjecture on its equality boundary and certifies 117 more cases, but the full conjecture remains open.

Mahmoodian and Mirzakhani posed the conjecture in 1995: for $r \le s \le t$ , the necessary parity, divisibility, and size conditions for decomposing $K(r,s,t)$ into $5$ -cycles should also be sufficient.

Known results

Equal part sizes: sufficiency was proved apart from the exceptional family $K(5x,5x,z)$ with $5 \nmid z$ (Mahmoodian–Mirzakhani, 1995).
All part sizes even, and several cases with equal or suitably divisible parts, were settled (Cavenagh–Billington, 2011).
Further infinite families include all parts divisible by $5$ under additional size restrictions (2019).
The odd, distinct-size case has remained the principal unresolved regime.

August 2026 boundary result

Bryant and Mačajová report a constructive proof of the equality-boundary case and computational certificates for 117 additional previously unresolved decompositions. Their preprint explicitly leaves the strict-interior cases open, so this is substantial partial progress rather than a solution of the conjecture.

Current status (as of August 2026): The equality-boundary case and 117 additional cases are settled in the new preprint, while the full conjecture for strict-interior triples remains open.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Completing the Boundary Case of the Mahmoodian-Mirzakhani Conjecture and 117 New Computational 5-Cycle Decompositions of Complete Tripartite Graphs — arXiv — Darryn Bryant, Barbara Mačajová

design-theory graph-decompositions

2 days ago