MathDB

n(\geq 4)

islands are connected by bridges to satisfy the following conditions:
[*]Each bridge connects only two islands and does not go through other islands. [*]There is at most one bridge connecting any two different islands. [*]There does not exist a list

A_1, A_2, \ldots, A_{2k}(k \geq 2)

of distinct islands that satisfy the following: For every

i=1, 2, \ldots, 2k

, the two islands

A_i

and

A_{i+1}

are connected by a bridge. (Let

A_{2k+1}=A_1

)
Prove that the number of the bridges is at most

\frac{3(n-1)}{2}

Problem Statement