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.

  • 3
    $\begingroup$ $f(k)$ is a maximum of what? What quantity does it denote? $\endgroup$
    – Shir
    Feb 10, 2012 at 22:30
  • $\begingroup$ 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? $\endgroup$ Feb 10, 2012 at 23:16
  • $\begingroup$ Apologies, I corrected the definition of $f(k)$. $\endgroup$ Feb 10, 2012 at 23:51
  • 2
    $\begingroup$ 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$. $\endgroup$ Feb 12, 2012 at 15:00
  • $\begingroup$ @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$. $\endgroup$ Feb 12, 2012 at 16:07

1 Answer 1


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

  • 2
    $\begingroup$ yippee. a cstheory.SE citation :) $\endgroup$ Mar 21, 2012 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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