MathCastle
Graph TheoryChallengeTrees

Trees · Challenge problem

The 2×42 \times 4 ladder graph has 22 rows of 44 vertices each: vertices 1,2,3,41,2,3,4 form the top row, vertices 5,6,7,85,6,7,8 form the bottom row. Horizontal edges connect 1-2,2-3,3-41\text{-}2, 2\text{-}3, 3\text{-}4 (top) and 5-6,6-7,7-85\text{-}6, 6\text{-}7, 7\text{-}8 (bottom); vertical edges connect 1-5,2-6,3-7,4-81\text{-}5, 2\text{-}6, 3\text{-}7, 4\text{-}8 (rungs). How many spanning trees does this graph have?