Nicole is running on a graph given by ‘edge’. She is now at vertex ‘x’ and needs to finish at home vertex ‘y’. Nicole wants to exercise as much as possible while she only has ‘n’ chocolate bars, each of which provides the energy for Nicole to run through a single edge. Yuan Yuan finds a route for Nicole to run. 



For example, let ‘edge’ be given by its edges as follows.

edge={a\[UndirectedEdge]b,b\[UndirectedEdge]c,c\[UndirectedEdge]d,d\[UndirectedEdge]e,e\[UndirectedEdge]a};

The graph looks like follows.

AdjacencyGraph[Normal[AdjacencyMatrix[edge]],VertexLabels->Table[i->Subscript[v,i],{i,First[Dimensions[Normal[AdjacencyMatrix[edge]]]]}]]

The function ‘walk’ tells the number of possible routes from ‘x’ to ‘y’ traversing exactly ‘n’ edges on ‘edge’. ‘M’ is the adjacency matrix: Entry (Subscript[M, i,j])=1 if and only if there is an edge between vertices i and j. It is known that the (i,j) entry in the nth power of ‘M’ gives the number of n-walks from i to j.

walk[edge_,x_,y_,n_]:= Module[{M,Mn,no},
M=Normal[AdjacencyMatrix[edge]];
Mn=MatrixPower[M,n];
no=Part[Mn,x,y]
]

The function ‘path’ gives a path randomly from ‘x’ to ‘y’ traversing exactly ‘n’ edges on ‘edge’, if there exists one.

path[edge_,x_,y_,n_]:=Module[{p,q,c,X,M=Normal[AdjacencyMatrix[edge]]},
(For[{p,c,X,q}={ToString[y/.i_->Subscript[v,i],StandardForm],1,y,""},c<n,c+=1,
X=RandomChoice[Level[Intersection[Position[MatrixPower[M,n-c][[x]],w_ /;w≠0],Position[MatrixPower[M,1][[X]],w_/;w≠0]],{2}]];
q=ToString[X/.i_:>Subscript[v,i],StandardForm];
p=q<>p];
ToString[x/.i_->Subscript[v,i],StandardForm]<>p)]

Try an example:

walk[edge,1,3,4]

path[edge,1,3,4]