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

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

• "the total number of paths in the graph that do not share any edge with the given path" Which path? With itself? Jun 11 '19 at 7:03
• do not share any edge with given path i.e the path from vertex a to b . you can go through the example that will clarify it more. Jun 11 '19 at 7:12
• You should probably make it clearer that, because the graph is acyclic (i.e., a forest), if a path exists from $a$ to $b$ (i.e., they are in the same component and, hence, in the same tree), then it is unique. Jun 11 '19 at 7:14
• I am failing to understand your doubt ,i will try to explain it once again . it is true that path from a to b will be unique , but we have to find pair of vertices (x,y) whose path does not share any edge with path (a,b) ,because if they do so then common vertices will be more than 1 . hence paths (x,y) which do not share any edge with (a,b) will have 0 or 1 vertices common with the path (a,b) , We have find the number pairs with 1 common vertex Jun 11 '19 at 7:43
• Your example is not clear. If you are given the actual path from $a$ to $b$ you should mention it clearly in the question, and write it in the example. Also note that not any acyclic graph has only one path between two vertices.
– lox
Jun 11 '19 at 8:34

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.

• can you please give me more information about the line ' The number of possible paths is the sum of the cross-products more the N paths having a as start ' and specifically ' cross-products more the N paths ' Jun 11 '19 at 20:11
• @tanishq sharma I added an example in my answer. "cross-products" is probably not the best word to describe this. It is just the analogy with multiplication, in my example $b*e*(c+d)$. Jun 13 '19 at 8:22