The Lovász-Cherkassky theorem for locally finite graphs with ends

Abstract

Lovász and Cherkassky discovered independently that, if $G$ is a finite graph and $T\subseteq V(G)$ such that the degree $d_G(v)$ is even for every vertex $v\in V(G)\setminus T$, then the maximum number of edge-disjoint paths which are internally disjoint from~$T$ and connect distinct vertices of $T$ is equal to $\frac{1}{2}{\sum }_{t\in T}{\lambda }_G(t,T\setminus \{t\})$ (where ${\lambda }_G(t,T\setminus \{t\})$ is the size of a smallest cut that separates $t$ and $T\setminus \{t\}$). From another perspective, this means that for every vertex $t\in T$, in any optimal path-system there are ${\lambda }_G(t,T\setminus \{t\})$ many paths between $t$ and~$T\setminus \{t\}$. We extend the theorem of Lovász and Cherkassky based on this reformulation to all locally-finite infinite graphs and their ends. In our generalisation, $T$ may contain not just vertices but ends as well, and paths are one-way (two-way) infinite when they establish a vertex-end (end-end) connection.

8 pages, equivalent but new statement of the main result

Cited by in corpus (1)

• Edge-connectivity between edge-ends of infinite graphs