MathDB

In a country between each pair of cities there is at most one direct road. There is a connection (using one or more roads) between any two cities even after the elimination of any given city and all roads incident to this city. We say that the city

A

can be k -directionally connected to the city

B

, if : we can orient at most

k

roads such that after arbitrary orientation of remaining roads for any fixed road

l

(directly connecting two cities) there is a path passing through roads in the direction of their orientation starting at

A

, passing through

l

and ending at

B

and visiting each city at most once. Suppose that in a country with

n

cities, any two cities can be k - directionally connected. What is the minimal value of

k

Problem Statement