MathCastle
Graph TheoryHardTrees

Trees · Hard problem

Network PP has vertices 11–66 and cables 12,23,34,41,45,56,6312, 23, 34, 41, 45, 56, 63 (two squares, 1-2-3-41\text{-}2\text{-}3\text{-}4 and 3-4-5-63\text{-}4\text{-}5\text{-}6, sharing edge 3434). Network QQ has the same 66 vertices wired as a hexagon 12,23,34,45,56,6112,23,34,45,56,61 plus two long chords 1414 and 2525. Which network has MORE spanning trees, and how many does it have?