# 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:

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

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

3. 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;

4. Any node should not be repeated in that sequence ;

How many such paths are there?

• Please use MathJax when formatting your question. See math.stackexchange.com/help/notation – user259242 Nov 5 '16 at 3:18
• @user259242 Sorry,I will make sure to use it. – sammy Nov 5 '16 at 3:43
• Your graph is a tree. I think that the answer depends on the graph shape, weights of its vertices, and given values of $Min$ and $Max$. – Alex Ravsky Nov 7 '16 at 9:01
• Can someone please explain the second condition in detail? – Shin Kim Nov 7 '16 at 9:32
• @AlexRavsky I fixed the question. Please check it out again. And the shape ,weight of it's vertices and value of $Min$ and $Max$ are given. – sammy Nov 7 '16 at 18:46

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