Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let $G$ be a simple graph on n nodes and let $s$ and $t$ be two nodes of $G.$ Suppose that number of (simple) paths from s to t in $G$ is at least $n^k.$ Then, is it possible to obtain a $\Omega(k)$-chain from $G$ with ($s$ and $t$ as endpoints) by a sequence of deletion and contraction of edges?
If the answer is positive then the second part of question is whether there is an efficient algorithm to obtain such a large chain.
I would be equally happy with $\sqrt k$-chain or $k^\alpha$ for any $\alpha >0.$
I would appreciate any partial answer or any intuition on whether such a conjecture should hold.
I had posted this on math overflow few days back. Someone suggested to post it here as well.