Do graphs with large number of paths contain large chain minor?

Question

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?

I would be equally happy with $\Omega(\sqrt k)$-chain or $\Omega(k^\alpha)$ for any $\alpha > 0.$

This question is closely related to another one that I asked few days ago: Do graphs with large number of cycles always contain large necklace minor?

I would appreciate any partial answer or any intuition on whether such a conjecture should hold.

Answer 1

No, there is no such bound.

Consider the graph $G_n$ whose vertices are pairs $(k,\nu) \in \{1, 2, \dots, n\} \times \{0, 1\}$, with edges between $(k, \nu)$ and $(k+1, \mu)$ for every $k \in \{0, 1, \dots, n-1\}$ and every $\nu, \mu \in \{0, 1\}$. Take $s = (n, 0)$ and $t = (n, 1)$. Then $\left|G_n\right|$ grows linearly in $n$, and the number of paths from $s$ to $t$ grows exponentially in $n$. However, $G_n$ has no 3-chain minors from $s$ to $t$.

We prove this by induction on $n$. Consider a $k$-chain minor of $G_n$ from $s$ to $t$. Let $H$ be the subgraph of $G$ obtained after all edge deletions, but before any contractions. If both $s$ and $t$ have degree 1 in $H$, then by the induction hypothesis $k \leq 2$. Otherwise, one of them has degree $2$, so there is a path of length $2$ in $H$ from $s$ to $t$, which means $k \leq 2$.

You can think of this as iterating the following construction. Given a graph with a specified source and sink, construct a new graph by adding two new vertices, the new source and the new sink, and four new edges, connecting the new source and sink to the old. Each iteration at least doubles the number of paths from source to sink, but adds no new $k$-chain minors for $k \geq 3$.

The idea behind the conjecture is that if a graph has many paths from $s$ to $t$, then it's because the graph can be cut into two independent parts, one with many paths from $s$ to some point $c$ and one with many paths from $c$ to $t$. As the above construction shows, though, even if all the paths pass through some point $c$, there may not be a consistent way to pick an "$s$-side" and a "$t$-side."