MathCastle
Graph TheoryHardWalks, Paths and Connectivity

Walks, Paths and Connectivity · Hard problem

Let GG have vertices 1,…,61,\ldots,6 and edges 12,23,1312,23,13 (a triangle on 1,2,31,2,3), the single bridge 3434, and 45,56,4645,56,46 (a triangle on 4,5,64,5,6). Among the walks of length 55 from vertex 11 to vertex 66, how many of them are actual paths (repeat no vertex)?