MathCastle
Graph TheoryHardWalks, Paths and Connectivity

Walks, Paths and Connectivity · Hard problem

Let GG be the "house" graph: a square on vertices 1,2,3,41,2,3,4 (edges 12,23,34,4112,23,34,41) with an apex vertex 55 joined to both 33 and 44. A trail of length 44 from 11 to 55 uses 44 distinct edges (no edge repeated), possibly revisiting a vertex. How many such trails are there?