MathDB

A city has

4

horizontal and

n\geq3

vertical boulevards which intersect at

4n

crossroads. The crossroads divide every horizontal boulevard into

n-1

streets and every vertical boulevard into

3

streets. The mayor of the city decides to close the minimum possible number of crossroads so that the city doesn't have a closed path(this means that starting from any street and going only through open crossroads without turning back you can't return to the same street).

a)

Prove that exactly

n

crossroads are closed.

b)

Prove that if from any street you can go to any other street and none of the

4

corner crossroads are closed then exactly

3

crossroads on the border are closed(A crossroad is on the border if it lies either on the first or fourth horizontal boulevard, or on the first or the n-th vertical boulevard).

Problem Statement