# Question:Number of possible paths of length k in any arbitrary graph G

## Question:Number of possible paths of length k in any arbitrary graph G

Maple
```restart;
with(GraphTheory);
with(combinat, cartprod);
with(SpecialGraphs);
with(RandomGraphs);
```

Given any arbitary graph G how many possible paths of length k are possible

G := CartesianProduct(PathGraph(3), PathGraph(3));
s := AllPairsDistance(FLT)

How to find how may possible paths of length say 4 from vertex 1:1

" for example this CartesianProduct(Path(3),Path(3)) number of possible paths of length 2 are

```1:1 - 1:2 -2:2

1:1 -2:1-2:2

1:1-1:2 -1:3

1:1-2:1-3:1```

so a total of 2 length paths

next say how may possible paths of length say 3 from vertex 1:2

similar given a vertex and path length how many possible path of that length are possible from that vertex.

It is not restricted to this graph given any graph G in general , a vertex v and k a path length i should get total number of paths of that length in that graph G

That is function say   F(G::Graph,vertex,k) i should get output of the number of path of length k from that vertex v.

"Only a idea but I may be wrong

I had an idea taking a row of a vertex in the graph G in the shortest path matrix and finding the number of possible totals which can get  length k I may be wrong to or correct but I finding to implement this in code neatly too.

That is if (0,1,2,1,3,4,1,2)

The number of possible 2 this are

```0+2=2

0+2=2

1+1=2

1+1=2

1+1=2```

So a total of 5 , 2 length path with respect to that vertex moving from left to right

Again if number of 3 length paths

Moving left to right

```0+3=3

1+2=3

1+1+1=3

1+2=3

2+1=3

2+1=3

1+2=3

1+2=3```

Total 8 paths of length 3

Until maximum possible length path from that vertex with respect to that graph.

Their is a mistake in the above logic is if the length paths intersection in some edges the path length will decrease so need to be careful so it looks difficult for me.

But I may be wrong in logic need help."

I am trying too