MathDB

Some of the

n + 1

cities in a country (including the capital city) are connected by one-way or two-way airlines. No two cities are connected by both a one-way airline and a two-way airline, but there may be more than one two-way airline between two cities. If

d_A

denotes the number of airlines from a city

A

, then

d_A \le n

for any city

A

other than the capital city and

d_A + d_B \le n

for any two cities

A

and

B

other than the capital city which are not connected by a two-way airline. Every airline has a return, possibly consisting of several connected flights. Find the largest possible number of two-way airlines and all configurations of airlines for which this largest number is attained.

Problem Statement