Finding a family of graphs that displays a certain characteristic

Question

I've read that the number of distinct paths in a graph can be exponential in relation to the number of vertices, later I encountered a problem which I spent some time trying to solve on my own.

The problem asks to find a family of undirected graphs in such a manner that every graph has a pair of vertices $s$ and $t$ such that the number of simple paths from $s$ to $t$ is at least $\Omega(2^n)$, where $n = |V|$.

I've tried applying this to a clique and a circular graph, but didn't really manage to find two (different) vertices that have this characteristic.

Not sure how to direct my thoughts from here.

Answer 1

Consider a clique $G=(V,E)$ on $n$ vertices and any two distinct nodes $s$ and $t$.

Any permutation $v_1, v_2, \dots, v_{n-2}$ of the vertices in $V \setminus \{s,t\}$ induces a simple path from $s$ to $t$, namely $\langle s, v_1, v_2, \dots, v_{n-2}, t \rangle$. Therefore the numebr of paths from $s$ to $t$ is at least: $$ (n-2)! = \Omega\left(\sqrt{n} \cdot \left( \frac{n-2}{e}\right)^{n-2}\right) = \omega(2^n), $$ where we used Stirling's inequality and, for $n \ge 14$: $$ \left( \frac{n-2}{e}\right)^{n-2}= 2^{(n-2) \log \frac{n-2}{e} } > 2^{(n-2) \log \frac{12}{3} } = 2^{2(n-2)} > 2^n. $$

As Pål GD points out, you can use an easier argument to get a weaker bound which is still enough for you needs. Fix an arbitrary order of vertices in $V \setminus \{s,t\}$ and notice that any subset $X$ of $V \setminus \{s,t\}$ induces a path from $s$ to $t$ that traverses the vertices in $X$ according the chosen order. Therefore there are at least $2^{n-2} = \Omega(2^n)$ paths from $s$ to $t$.