Tag: AttilaJoo

The local connectivity  ${\kappa }_D(r,v)$ from $r$ to $v$ is defined to be the maximal number of internally disjoint $r\to v$ paths in $D$. A spanning subdigraph $L$ of $D$ with ${\kappa }_L(r,v)={\kappa }_D(r,v)$ for every $v\in V-r$ must have at least $\sum _{v\in V-r}{\kappa }_D(r,v)$ edges. It was shown by Lovász that, maybe surprisingly, this lower bound is sharp for every finite digraph. The optimality of an $L$ can be captured by the following characterization: For every $v\in V-r$ there is a system ${\mathcal{P}}_v$ of internally disjoint $r\to v$ paths in $L$ covering all the ingoing edges of $v$ in $L$ such that one can choose from  each $P\in {\mathcal{P}}_v$ either an edge or an internal vertex in such a way that the resulting set meets every $r\to v$ path of $D$. We prove that every digraph of size at most ${\mathrm{\aleph }}_1$  admits such a spanning subdigraph $L$. The question if this remains true for larger digraphs remains open.