how to find total paths in a graph which have only one vertex common with a given path

Question

Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.

How can I find the total number of paths in the graph that do not share any edge with the (unique) path from $a$ to $b$ and have only one vertex in common with it?

For example, suppose I have following graph :

and am given $a=4$, $b=5$. Then there are six paths satisfying the above condition: $(1,1)$, $(1,3)$, $(2,2)$, $(2,6)$, $(4,4)$, $(5,5)$ where $(x,y)$ is the path from $x$ to $y$.

Answer 1

Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ vertices of the given path more some of the other nodes.

Let's take $T$, one of these tree containing the vertex $a$ of the given path and a total of $n$ vertices. You want to compute the number of different paths passing through $a$. There are two possibilities:

• either $a$ has only one neighbour: then the possible paths are the $N$ paths ($a$, $i$) with $i \in N$
• either $a$ has several neighbours: then count the number of vertices in the subtree of each of these neighbours. The number of possible paths is the sum of the cross-products more the $N$ paths having $a$ as start.

Note that $T$ may have between $n$ and $n^2$ paths through $a$.

To answer your question, just sum all the trees' number of paths.

EDIT: small examples

If the tree has 4 vertices called $a,b,c,d$, connected linearly like that $a-b-c-d$ with $a$ being the vertex of the given path. Then $a$ has only 1 neighboor and the possible paths are all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d)$]

If the tree has 5 vertices $a $(of the given path)$, b, c, d, e$ connected like that:

    b-a-c-d
      |
      e

Then $a$ has 3 neighboors leading to the 3 subtrees: $b, c-d$ and $e$. The possible paths are:

• all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d), (a,e)$]
• the cross-products between $b$ and $c-d$: [$(b, c), (b, d)$]
• the cross-products between $e$ and $c-d$: [$(e, c), (e, d)$]
• the cross-products between $b$ and $e$: [$(b, e)$]

total 10 paths.