MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

A network has a main line of routers 1-2-3-4-5-6-71\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}7 (a path), with one extra router 88 attached directly to router 44. What is the size of a maximum matching (pairs of routers linked directly, each router in at most one pair)?