On partitioning the edges of an infinite digraph into directed cycles

The presence of various important substructures in combinatorics is often characterised by the lack of a simple natural obstacle. A classical example is the existence of a perfect matching in a bipartite graph: clearly, a bipartite graph can have a perfect matching only if any $k$ vertices from the same color class together have at least $k$ neighbors. Hall’s Theorem asserts that this necessary condition is in fact sufficient. Other classical results of this kind include Dilworth’s Theorem on partitioning of partially ordered sets into disjoint chains, Menger’s Theorem on the existence of disjoint paths and Nash-Williams Theorem on the existence of edge-disjoint spanning trees.

This article concerns the problem of partitioning the edges of a graph into cycles. In the undirected case, the presence of a finite odd cut prevents the existence of such a partition. In 1960, Nash-Williams proved that this necessary condition is sufficient. While this is very easy to prove when the graph in question is finite and moderately easy when it is countable, the proof becomes surprisingly complex for uncountable graphs. In 2017, Thomassen gave a more elementary proof of this result and conjectured that the following clearly necessary condition is sufficient in the directed case: a directed graph has an edge partition into directed cycles if and only if every cut is balanced, i.e., the cardinalities of the sets of edges directed from the first part to the other and from the other part to the first are the same. The author of this article proves this conjecture.