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 Łuczak, Rödl and Szemerédi [T. Łuczak, V. Rödl, E. Szemerédi, 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].