All graphs with maximum degree three whose complements have 4-cycle decompositions (Q924981)

A \(k\)-cycle system of a graph \(G\) is a partition of the edges of \(G\) into sets each of which induces a cycle of length \(k\). In the paper under review the authors classify the graphs of \(n\) vertices and maximal degree 3 whose complement in the complete graphs \(K_n\) admits a 4-cycle system. The main result shows that, with two explicitly shown exceptions, such graphs \(G\) of \(n\) vertices have to satisfy two conditions: all vertices must have odd degree and the number \(n(n-1)/2-|F(G)|\) must be divisible to 4.