MathCastle
Graph TheoryHardTrees

Trees · Hard problem

Two 44-cycles, 1-2-3-4-11\text{-}2\text{-}3\text{-}4\text{-}1 and 5-6-7-8-55\text{-}6\text{-}7\text{-}8\text{-}5, are joined by two separate connecting edges, 1515 and 2626 (vertices 1,…,81,\ldots,8; edges 12,23,34,41,56,67,78,85,15,2612,23,34,41,56,67,78,85,15,26). How many spanning trees does this graph have?