Decomposing Graphs of High Minimum Degree into 4‐Cycles

If a graph G decomposes into edge‐disjoint 4‐cycles, then each vertex of G has even degree and 4 divides the number of edges in G . It is shown that these obvious necessary conditions are also sufficient when G is any simple graph having minimum degree at least ( 31 32 + o n ( 1 ) ) n , where n is the number of vertices in G . This improves the bound given by Gustavsson (PhD Thesis, University of Stockholm, 1991), who showed (as part of a more general result) sufficiency for simple graphs with minimum degree at least ( 1 − 10 − 94 + o n ( 1 ) ) n . On the other hand, it is known that for arbitrarily large values of n there exist simple graphs satisfying the obvious necessary conditions, having n vertices and minimum degree3 5 n − 1 , but having no decomposition into edge‐disjoint 4‐cycles. We also show that if G is a bipartite simple graph with n vertices in each part, then the obvious necessary conditions for G to decompose into 4‐cycles are sufficient when G has minimum degree at least ( 31 32 + o n ( 1 ) ) n .