The Lovász-Cherkassky theorem in countable graphs
Attila Joó · Journal of Combinatorial Theory Series B · 2022
Lovász and Cherkassky discovered in the 1970s independently that if G is a finite graph with a given set T of terminal vertices such that G is inner Eulerian with respect to T, then the maximal number of edge-disjoint paths connecting distinct vertices in T is ∑t∈Tλ(t,T−t) where λ is the local edge-connectivity function. The optimality of a system of edge-disjoint T-paths in the Lovász-Cherkassky theorem is witnessed by the existence of certain cuts by Menger's theorem. The infinite generalisation of Menger's theorem by Aharoni and Berger (earlier known as the Erdős-Menger Conjecture) together with the characterization of infinite Eulerian graphs due to Nash-Williams makes it possible to generalise the theorem for infinite graphs in a structural way. The aim of this paper is to formulate this generalisation and prove it for countable graphs.