MathDB

Let

M

be a map made of several cities linked to each other by flights. We say that there is a route between two cities if there is a nonstop flight linking these two cities. For each city to the

M

denote by

M_a

the map formed by the cities that have a route to and routes linking these cities together ( to not part of

M_a

). The cities of

M_a

are divided into two sets so that the number of routes linking cities of different sets is maximum; we call this number the cut of

M_a

. Suppose that for every cut of

M_a

, it is strictly less than two thirds of the number of routes

M_a

. Show that for any coloring of the

M

routes with two colors there are three cities of

M

joined by three routes of the same color.

3

Problems(1)