MathDB

Let

N

and

d

be two positive integers with

N\geq d+2

. There are

N

countries connected via two-way direct flights, where each country is connected to exactly

d

other countries. It is known that for any two different countries, it is possible to go from one to another via several flights. A country is \emph{important} if after removing it and all the

d

countries it is connected to, there exist two other countries that are no longer connected via several flights. Show that if every country is important, then one can choose two countries so that more than

2d/3

countries are connected to both of them via direct flights.
Proposed by usjl

Problem Statement