# From edge-disjoint paths to independent paths

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.

• $f(k)$ is a maximum of what? What quantity does it denote?
– Shir
Commented Feb 10, 2012 at 22:30
• Some doubts: in a graph $G \in \mathcal{G}_k$, are other non $k$ edge-disjoint paths allowed between $x$ and $y$? A graph $G \in \mathcal{G}_k$ must contain at least one pair of vertices $x$ and $y$ connected with $k$ disjoint edges? or exactly one pair? What about a graph that contais a pair of vertices connected with $k$ disjoint edges and also a pair of vertices connected with $k+1$ disjoint edges? Commented Feb 10, 2012 at 23:16
• Apologies, I corrected the definition of $f(k)$. Commented Feb 10, 2012 at 23:51
• I could be mistaken but it seems that the well-known series parallel graph (the recursive diamond graph, see cseweb.ucsd.edu/~dasgupta/254-embeddings/claire.pdf) can be used to show that $f(k) = 2$ for any value of $k$. Commented Feb 12, 2012 at 15:00
• @ChandraChekuri: Actually, for the diamond graph $G_2$, we have two vertices $s,t$ with $4$ edge-disjoint $s-t$ paths, but we have 3 independent $x'-y'$ paths, where $x'=s$ and $y'$ is one of the 2 degree-4 vertices besides $s$ and $t$. I believe that these graphs can be used, though, to show that $f(k)=3$ for any $k\ge 3$. Commented Feb 12, 2012 at 16:07

## 1 Answer

It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See arXiv:1203.4483 for a proof.

• yippee. a cstheory.SE citation :) Commented Mar 21, 2012 at 16:49