MathDB

The road ministry has assigned

80

informal companies to repair

2400

roads. These roads connect

100

cities to each other. Each road is between

2

cities and there is at most

1

road between every

2

cities. We know that each company repairs

30

roads that it has agencies in each

2

ends of them. Prove that there exists a city in which

8

companies have agencies.

Problem Statement