Cono Sur Olympiad 2013, Problem 3
Source:
August 22, 2014
combinatorics proposedcombinatorics
Problem Statement
Nocycleland is a country with cities and two-way roads, each one of them connecting two cities. A city neighbors if there is one road that connects them, and a city quasi-neighbors if there is a city such that neighbors and neighbors .
It is known that in Nocycleland, there are no pair of cities connected directly with more than one road, and there are no four cities , , and such that neighbors , neighbors , neighbors , and neighbors .
Show that there is at least one city that quasi-neighbors at least other cities.