<p>It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See <a href="http://arxiv.org/abs/1203.4483" rel="noreferrer">arXiv:1203.4483</a> for a proof.</p>

CC BY-SA 3.0
2012-03-21T16:49:29.060Z
yippee. a cstheory.SE citation :)
Suresh Venkat
CC BY-SA 3.0
2012-03-21T07:35:32.100Z
2012-03-21T07:35:32.100Z
Serge Gaspers
<p>Let $\mathcal{G}_k$ denote the set of all graphs that contain two vertices $x,y$
and $k$ edge-disjoint $x-y$ paths.</p>

<p>Define $f(k)$ to be the maximum such that for every graph $G\in \mathcal{G}_k$
there are two vertices $x&#39;,y&#39;$ with $f(k)$ independent $x&#39;-y&#39;$ paths in $G$.</p>

<p>Here, a set of paths is <em>independent</em> if none contains an internal vertex of another.</p>

<p>Are any lower bounds for $f(k)$ known in the literature? </p>

<p>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.</p>

<p>As a different formulation, how large can you make $f(k)$ in the following statement?</p>

<blockquote>
  <p>If $G$ is an undirected graph containing two vertices $x,y$ and $k$ edge-disjoint $x-y$ paths, then $G$ contains two vertices $x&#39;,y&#39;$ with $f(k)$ independent $x&#39;-y&#39;$ paths.</p>
</blockquote>

CC BY-SA 3.0
2012-02-10T22:30:50.677Z
$f(k)$ is a maximum of what? What quantity does it denote?
Shir
CC BY-SA 3.0
2012-02-10T23:16:20.473Z
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
CC BY-SA 3.0
2012-02-10T23:51:45.967Z
Apologies, I corrected the definition of $f(k)$.
Serge Gaspers
CC BY-SA 3.0
2012-02-12T15:00:53.897Z
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
CC BY-SA 3.0
2012-02-12T16:07:49.100Z
@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
CC BY-SA 3.0
2012-03-07T15:42:47.473Z
Maybe one of you could write an answer with this argument.
Vinicius dos Santos
<reference-request><graph-theory><co.combinatorics>
From edge-disjoint paths to independent paths
Serge Gaspers
# From edge-disjoint paths to independent paths

(Asked by: username_0 on 2012-02-10)

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.

**Tags:** reference-request, graph-theory, co.combinatorics

> **Comments:**
> **username_1**: $f(k)$ is a maximum of what? What quantity does it denote?  
> **username_2**: 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?  
> **username_0**: Apologies, I corrected the definition of $f(k)$.  
> **username_3**: 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$.  
> **username_0**: @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$.  
> **username_4**: Maybe one of you could write an answer with this argument.  

---

## 1 answers

### Answer by username_0 on 2012-03-21. Score: 5 | Accepted answer

It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See [arXiv:1203.4483](http://arxiv.org/abs/1203.4483) for a proof.

> **Comments:**
> **username_5**: yippee. a cstheory.SE citation :)  

---

