you can get from 1 to another by taking buses that only pass through cities in
Source: Mathematics Regional Olympiad of Mexico Center Zone 2016 P6
November 12, 2021
combinatorics
Problem Statement
In Tlaxcala, there is a transportation system that works through buses that travel from one city to another in one direction . A set of cities is said beautiful if it contains at least three different cities and from each city in at least two buses depart, each one goes directly to a different city in and none of them is (if there is a direct bus from to a city in , there is not necessarily a direct bus from to ). Show that if there exists a beautiful set of cities , then there exists a beautiful subset of , such that for any two cities in , you can get from one to another by taking buses that only pass through cities in . Note: A bus goes directly from one city to another if it does not pass through any other city.