MathDB

There are

n(n\ge 8)

airports, some of which have one-way direct routes between them. For any two airports

a

and

b

, there is at most one one-way direct route from

a

b

(there may be both one-way direct routes from

a

b

and from

b

a

). For any set

A

composed of airports

(1\le | A| \le n-1)

, there are at least

4\cdot \min \{|A|,n-|A| \}

one-way direct routes from the airport in

A

to the airport not in

A

. Prove that: For any airport

x

, we can start from

x

and return to the airport by no more than

\sqrt{2n}

one-way direct routes.

Problem Statement