Number of paths from A to B of length N

Question

Let G = (V, E) be the graph in the figure below. How many paths are there from A to D? How many paths of those paths have length 6?

I know the number of paths from A to D of length 6 is 8, but I have no idea how to get to that answer without straight up counting each and every single path.

Is there also a method that could extend to a larger graph, like the graphs below? For example, how would I find the number of paths of length 6 from vertex 1 to 2?

Answer 1

Here's a hint: all paths from A to D will have to go through F. So you can ask how many paths there are from A to F, and how many there are from F to D, and you can match up their lengths. (For instance, if you want a total path of length 6, then you can only match up a path from A to F of length 4 with a path from F to D of length 2, as 4 + 2 = 6.)

In the case of your final graph, there's a very easy answer: any path of length 6 must go through 7 vertices (including the start and end vertices), and there aren't 7 vertices here, so there are no such paths.

The other graph: well, this graph is complete, so it suffices to simply choose an order in which you go through the vertices: 1 _ _ _ _ _ 2. So there are $10\times 9\times 8\times 7\times 6$ such paths.

For general graphs - which usually won't be complete, might be quite large, and won't have these 'bottlenecks' like the vertex F - I imagine there's no 'nice' method, and you'll have to do something ad hoc. For example, split it into subquestions: "how many paths are there that don't go through vertices X, Y and Z?", "how many paths are there that go through X but not Y or Z?", etc.

For example, take the complete graph on 10 vertices like in your second picture, and add in an 11th vertex which is only connected to a few of the other vertices: then you can ask "how many paths don't go through vertex 11?", and "if a path goes through vertex 11, where along the path can vertex 11 be?", and "suppose the third (second, fourth, fifth) vertex of a path is vertex 11: how many choices are there for the rest of the vertices?", and so on.

Answer 2

I see that the specific question has already been satisfactorily addressed. I'd like to present an idea for the more general question.

Given any simple, undirected graph with $N$ vertices, one can associate an $N$x$N$ matrix, $A$, called the adjacency matrix to it where the element $A_{ij}$ is 1 if the $i^{th}$ and $j^{th}$ vertices are connected and 0 otherwise. If you look at the powers of $A$, i.e. $A^k$, you'll realize that the $(ij)^{th}$ element of this matrix is nothing but the number of $walks$ of length $k$ from $i$ to $j$. If you'd like to prove this, try induction. But the above method only gives the number of walks. How you'd infer the number of paths from it is still a challenge but a doable one. (I think)

Another problem that I see with this method is that evaluating powers of a large matrix can be very computationally taxing. But since $A$ is real and symmetric, one can diagonalize it and find a way around it (since the powers of a diagonal matrix is a diagonal matrix with each element raised to that power).