Undirected Connected Graph : Number of unique path Given an undirected connected graph with $N$ nodes and $N-1$ edges, a path $P_1P_2\cdots P_i$ is defined as follows:


*

*Nodes $P_j$ and $P_{j+1}$ are connected by an edge for each $\left({1}\right) <= \left({j}\right) <= \left({i}\right)$;

*The weight of a $Pth$ node is given as $P_k$;

*The number of indices $j$ with $\left({1}\right) < \left({j}\right) < \left({i}\right)$ such that $\left(P_{k_{j-1}}\right) < \left(P_{k_{j}}\right)$ and $\left(P_{k_{j}}\right) > \left(P_{k_{j+1}}\right)$ is at least Min and at most Max for some given Min and Max;

*Any node should not be repeated in that sequence ;
How many such paths are there?
 A: Without specific conditions imposed on the shape of the graph $G$, weights $w(v)$ of its nodes $v$, the given  values $Min$ and $Max$ I can propose a straightforward algorithm, which has a complexity polynomial with the respect to the number of nodes of the graph $G$.
Let $v$ and $u$ be arbitrary nodes of the graph $G$. Let the number of peaks $p(v,u)$ be the number of indices $j$, ($1<j<i$) such that $w(v_{j-1})< w(v_{j})< w(v_{j+1})$, where $v=v_0,v_1\dots, v_{i-1}, v_{k}=u$ is the unique simple path between these nodes. 
First of all we do a preprocessing which calculates the number of peaks $p(v,u)$ on the simple path between each pair $v$ and $u$ of nodes of the graph $G$ and the first node $n(v,u)$ on these path. This can be done recursively as follows. Let $v$ be a leaf of the graph $G$. Calculate the number of peaks and the first node on the simple path between each pair of nodes of the induced graph $G - v$. Let $u$ be a unique neighbor of the node $v$. Put $n(v,u)=u$, $n(u,v)=v$, and for each node $u’\ne u$ of the graph  $G- v$ put $n(u’,v)=n(u’,u)$,  $n(v,u’)=u$, and 
$$p(u’,v)=\cases{p(u’,u)+1, \mbox{if $w(v)<w(u)>w(n(v,u’))$},\\ 
p(u’,u), \mbox{otherwise}}.$$ 
Now the quantity which you are asking for is the number $N$ of pair $\{v,u\}$ of nodes of the graph $G$ such that 
$$Min\le p(v,u)\le Max.$$
