Minimum Size of Largest Connected Component in $3$-Colored Complete Graph
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 11.8
April 5, 2023
combinatoricsgraphsgraph theory
Problem Statement
There are cities in a country, every two of which are bidirectionally connected by exactly one of three modes of transportation - rail, air, or road. A tourist has arrived in this country and has the entire transportation scheme. He chooses a travel ticket for one of the modes of transportation and the city from which he starts his trip. He wants to visit as many cities as possible, but using only the ticket for the specified type of transportation. What is the largest for which the tourist will always be able to visit at least cities? During the route, he can return to the cities he has already visited.Proposed by Bogdan Rublov