MathDB

A country with

n

cities has some two-way roads connecting certain pairs of cities. Someone notices that if the country is split into two parts in any way, then there would be at most

kn

roads between the two parts (where

k

is a fixed positive integer). What is the largest integer

m

(in terms of

n

and

k

) such that there is guaranteed to be a set of

m

cities, no two of which are directly connected by a road?

Problem Statement