4-cycle in a graph
Source: Indonesian MO (INAMO) 2009, Day 1, Problem 4
August 8, 2009
floor functioncombinatorics unsolvedcombinatorics
Problem Statement
In an island, there exist 7 towns and a railway system which connected some of the towns. Every railway segment connects 2 towns, and in every town there exists at least 3 railway segments that connects the town to another towns. Prove that there exists a route that visits 4 different towns once and go back to the original town. (Example: A\minus{}B\minus{}C\minus{}D\minus{}A)