MathDB

There are 1000 towns

A_{1},A_{2},\ldots ,A_{1000}

with airports in a country and some of them are connected via flights. It's known that the

i

-th town is connected with

d_{i}

other towns where

d_{1}\leq d_{2}\leq \ldots \leq d_{1000}

and

d_{j}\geq j+1

for every

j=1,2,\ldots 999-d_{999}

. Prove that if the airport of any town

A_{k}

is closed, then we'd still be able to get from any town

A_{i}

to any

A_{j}

for

i,j\neq k

(possibly by more than one flight).

Problem 11.4