Problem

Source: Macedonian Mathematical Olympiad 2021 P2

Tags: combinatorics, graph theory



In the City of Islands there are 2021 islands connected by bridges. For any given pair of islands A and B, one can go from island A to island B using the bridges. Moreover, for any four islands A1,A2,A3 and A4: if there is a bridge from Ai to Ai+1 for each i{1,2,3}, then there is a bridge between Aj and Ak for some j,k{1,2,3,4} with |jk|=2. Show that there is at least one island which is connected to any other island by a bridge.