1
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ This solution is really good, thank you for sharing! $\endgroup$
    – Aishgadol
    Nov 7 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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