Let $\mathcal{G}_k$ denote the set of all graphs that contain two vertices $x,y$and $k$ edge-disjoint $x-y$ paths.Define $f(k)$ to be the maximum such that for every graph $G\in \mathcal{G}_k$there are two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths in $G$.Here, a set of paths is independent if none contains an internal vertex of another.Are any lower bounds for $f(k)$ known in the literature? In particular, I need $f(3)=3$ in an algorithm where I need to find some obstructions in a graph.This is not hard to prove, but I'm wondering whether it is known in the literature, maybe as a special case of a more general theorem.As a different formulation, how large can you make $f(k)$ in the following statement?If $G$ is an undirected graph containing two vertices $x,y$ and $k$ edge-disjoint $x-y$ paths, then $G$ contains two vertices $x',y'$ with $f(k)$ independent $x'-y'$ paths.
From edge-disjoint paths to independent paths
reference request;graph theory;co.combinatorics
It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See arXiv:1203.4483 for a proof.