MathCastle
Graph TheoryHardWalks, Paths and Connectivity

Walks, Paths and Connectivity · Hard problem

A wheel graph has a hub vertex 00 joined to every vertex of a 55-cycle 1-2-3-4-5-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1 (edges 12,23,34,45,51,01,02,03,04,0512,23,34,45,51,01,02,03,04,05). A second, separate graph has two triangles a,b,ca,b,c and d,e,fd,e,f, joined by a single bridge cdcd (edges ab,bc,ca,de,ef,fd,cdab,bc,ca,de,ef,fd,cd). How many MORE triangles does the wheel graph have than the second graph?