MathDB

In a certain country there are

n

cities. Some pairs of cities are connected by highways in such a way that for each two cities there is at most one highway connecting them. Assume that for a certain positive integer

k

, the total number of highways is greater than

\frac{nk}{2}

. Show that there exist

k+2

distinct cities

C_1, C_2, \dots, C_{k+2}

such that

C_i

and

C_{i+1}

are connected by a highway for

i=1, 2, \dots, k+1

.
Proposed by Oriol Solé

Problem Statement