MathCastle
Graph TheorySuperchallengeWalks, Paths and Connectivity

Walks, Paths and Connectivity · Superchallenge problem

A graph has a central path 0-1-2-3-4-5-60\text{-}1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6, with a triangle attached at vertex 00 (extra vertices 7,87,8) and a triangle attached at vertex 66 (extra vertices 9,109,10). Among the 66 bridges of this graph, find the smallest possible difference between the sizes of the two pieces that removing a single bridge creates.