MathCastle
Graph TheoryEasyBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Easy problem

Six guard posts 1,2,…,61,2,\dots,6 are arranged in a ring, each able to monitor the two links to its neighbors in the cycle 1-2-3-4-5-6-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1. What is the minimum number of posts that must be staffed so every link in the ring is monitored by at least one staffed post?