Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
$f(k)$ is a maximum of what? What quantity does it denote? –  Shir Feb 10 '12 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? –  Marzio De Biasi Feb 10 '12 at 23:16
Apologies, I corrected the definition of $f(k)$. –  Serge Gaspers Feb 10 '12 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$. –  Chandra Chekuri Feb 12 '12 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$. –  Serge Gaspers Feb 12 '12 at 16:07
show 1 more comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
yippee. a cstheory.SE citation :) –  Suresh Venkat Mar 21 '12 at 16:49
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.