MathCastle
Graph TheorySuperchallengeWalks, Paths and Connectivity

Walks, Paths and Connectivity · Superchallenge problem

Let GG be three copies of K4K_4 in a chain: K4K_4 on {0,1,2,3}\{0,1,2,3\}, then bridge 3434, K4K_4 on {4,5,6,7}\{4,5,6,7\}, then bridge 7878, K4K_4 on {8,9,10,11}\{8,9,10,11\}. Find the maximum number of pairwise internally-disjoint paths between 00 and 1010 (in different end blocks), PLUS the maximum number between 00 and 22 (both in the first block).