OSN 2009 Problem 4

I proposed this problem to OSN (Indonesian Science Olympiad) 2009 committee and it was selected as problem #4.

There are 7 cities that are connected by a railroad network. Each railroad segment connects two cities, and each city is connected by at least 3 segments. Prove that there is a route that visits exactly 4 cities, visits them exactly once, and goes back to the city of origin.

(Example: A-B-C-D-A)

Official solution:

Take a city $A$ and let $B_1, B_2, B_3$ be the cities that it's connected to. Let $C_1,C_2,C_3$ be the remaining cities.

If there are two $B$ cities $B_i,B_j$ that are connected to a single $C$ city $C_k$, then we are done, because we have route $A - B_i - C_k - B_j - A$.

If there are two segments of the form $B_iB_j$, say $B_1B_2$ and $B_2B_3$, then we have route $A - B_1 - B_2 - B_3 - A$

If there is exactly one segment of the form $B_iB_j$, say $B_1B_2$, then each of $B_1,B_2$ must be connected to at least one $C$ city. Also, because $B_3$ is not connected to $B_1,B_2$, then it must be connected to two $C$ cities. There are 4 connections to $C$ cities but only 3 cities available, so we must have two distinct $B$ cities connecting to the same $C$ city.

If there is no segment of the form $B_iB_j$, then each $B$ city is connected to two $C$ cities. There are 6 connections but only 3 cities available, so once again we have two distinct $B$ cities connecting to the same $C$ city.

Alternative Solution

(by EddyHermanto in the Olimpiade forum)

Each segment connects two cities, so the total number of segments in all cities must be divisible by two. Since 7 x 3 = 21, then we cannot have all cities connected by exactly 3 segments. Thus there is a city $A$ connected by 4 segments to $B_1, B_2, B_3, B_4$. Let the remaining cities be $C_1, C_2$

If there are two $B$ cities $B_i,B_j$ that are connected to a single $C$ city $C_k$, then we are done, because we have route $A - B_i - C_k - B_j - A$. But the connection option for a $C$ city is limited to $A$, the other $C$ city, and the $B$ cities.

Thus in order for $C$ cities not to have connections two two $B$ cities, each $C$ city must connected to exactly one $B$ city, to $A$, and to the other $C$ city. So now we have a route in the form of $A - B_i - C_1 - C_2 - A$