MathCastle
Graph TheoryMediumWalks, Paths and Connectivity

Walks, Paths and Connectivity · Medium problem

A graph on vertices 1,2,3,4,51,2,3,4,5 consists of a square 1-2-3-4-11\text{-}2\text{-}3\text{-}4\text{-}1 with an extra vertex 55 joined to both 11 and 22 (edges 12,23,34,41,15,2512,23,34,41,15,25). How many distinct paths (no repeated vertex) of length exactly 33 run from vertex 44 to vertex 55?