Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture

We prove that every graph G has a vertex partition into a cycle and an anticycle (a cycle in the complement of G). Emptyset, singletons and edges are considered as cycles. This problem was posed by Lehel and shown to be true for very large graphs by Luczak, Rodl and Szemeredi IT. Luczak, V. Rodl, E. Szemeredi, Partitioning two-colored complete graphs into two monochromatic cycles, Combin. Probab. Comput. 7 (1998) 423-436], and more recently for large graphs by Allen [P. Allen, Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles, Combin. Probab. Comput. 17 (2008) 471-486]. (C) 2009 Elsevier Inc. All rights reserved.