MathCastle
Graph TheoryMediumGraph Coloring

Graph Coloring · Medium problem

A hub satellite 00 relays directly to 44 ground stations 1,2,3,41,2,3,4, which also form a ring among themselves (1-2,2-3,3-4,4-11\text{-}2,2\text{-}3,3\text{-}4,4\text{-}1), giving 88 links in all. Links meeting at the same station need different frequencies. What is the fewest frequencies needed?