Graph with Tokyo flavortext
Source: Swiss TST 2023 P5
September 8, 2023
combinatorics
Problem Statement
The Tokyo Metro system is one of the most efficient in the world. There is some odd positive integer such that each metro line passes through exactly stations, and each station is serviced by exactly metro lines. One can get from any station to any otherstation using only one metro line - but this connection is unique. Furthermore, any two metro lines must share exactly one station. David is planning an excursion for the IMO team, and wants to visit a set of stations. He remarks that no three of the stationsin are on a common metro line. Show that there is some station not in , which is connected to every station in by a different metro line.