

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Given an undirected graph $G$ and vertices $s, t$, are there any upper bounds on the number of simple paths from $s$ to $t$?

Can these bounds be improved if you know

1) The distance from $s$ to $t$

2) The graph has max degree $\Delta$

3) No two non-adjacent vertices on the path are allowed to be neighbors. For example if $x, y, z$ is a path, and $x$ is a neighbor of $z$, we would disallow that path

I tried looking on Google but I don't know what the keyword would be. Any pointers to papers or keywords would be great!

Thanks for the help.

share|cite|improve this question
up vote 3 down vote accepted

If the distance from s to t is 1, or the max degree is 2, then there are at most 2 such paths. Otherwise there are potentially exponentially many such paths even among cubic graphs (think of a cycle of diamonds). Of course, I am considering the extreme case and not looking at forests or other classes of graphs with few cycles. You may get a better answer if you know things like the girth of the graph and the cycle count and arrangement.

Gerhard "Ask Me About System Design" Paseman, 2012.01.11

share|cite|improve this answer

I would comment if I could, but since I can't, it goes as an answer.

The keyword you are looking for in Property 3 is "Induced Path".

share|cite|improve this answer

Your Answer


