MathCastle
Graph TheoryChallengeWalks, Paths and Connectivity

Walks, Paths and Connectivity · Challenge problem

Vertices s=1s=1 and t=2t=2 are joined by three internally-disjoint paths: 1-3-21\text{-}3\text{-}2 (length 22), 1-4-5-21\text{-}4\text{-}5\text{-}2 (length 33), and 1-6-7-8-21\text{-}6\text{-}7\text{-}8\text{-}2 (length 44), and by no other edges. What is the maximum number of pairwise internally-disjoint paths from 11 to 22?