MathCastle
Graph TheoryEasyBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Easy problem

A network wires nine computers 1,2,…,91,2,\dots,9 as a tree: the path 1-2-3-4-5-61\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6, together with three extra direct links, 77 to 22, 88 to 55, and 99 to 11. Every tree is bipartite, so the nine computers split into two groups with every wire joining one group to the other. What is the size of the LARGER group?