MathDB

Let

n

be a positive integer. There are

n

islands with

n-1

bridges connecting them such that one can travel from any island to another. One afternoon, a fire breaks out in one of the islands. Every morning, it spreads to all neighbouring islands. (Two islands are neighbours if they are connected by a bridge.) To control the spread, one bridge is destroyed every night until the fire has nowhere to spread the next day. Let

X

be the minimum possible number of bridges one has to destroy before the fire stops spreading. Find the maximum possible value of

X

over all possible configurations of bridges and island where the fire starts at.

Problem Statement