Decomposing complete tripartite graphs into cycles of lengths 3 and 4 (Q1292817): Difference between revisions

It is shown that the complete tripartite graph \(K_{r,s,t}\), \(r \leq s \leq t\), has an edge-disjoint decomposition into \(a\) cycles of length 3 and \(b\) cycles of length 4 if and only if (1) \(r,s,t\) have the same parity, (2) if \(r\) is even, or if \(r\) is odd and \(s-r \equiv 0 \pmod {4}\), then \(a \leq rs\), (3) if \(r\) is odd and \(s-r \equiv 2 \pmod {4}\), then \(a \leq rs-2\), (4) the value of \(a\) decreases from its maximum value in steps of size 4, down to 0 if \(r\) is even and to 1 if \(r\) is odd.