MathDB
Travelling between n cities using minimum planes.

Source:

October 9, 2010
graph theorycombinatorics unsolvedcombinatorics

Problem Statement

One country has nn cities and every two of them are linked by a railroad. A railway worker should travel by train exactly once through the entire railroad system (reaching each city exactly once). If it is impossible for worker to travel by train between two cities, he can travel by plane. What is the minimal number of flights that the worker will have to use?