# The Country Of Brilliant

The country of Brilliant has $$2015$$ towns. Some pairs of towns are connected via two-way railroads. No town is connected to itself.

A set $$S= \{a_1, a_2, \cdots , a_n\}$$ of towns is called good if $$|S|= n>2$$ is even, and $$a_2$$ is connected to $$a_1$$, $$a_3$$ is connected to $$a_2$$, $$\cdots$$ , $$a_n$$ is connected to $$a_{n-1}$$ and $$a_1$$ is connected to $$a_n$$ (note that connectivity is mutual, i.e. if $$x$$ is connected to $$y$$, $$y$$ is connected to $$x$$). In other words, a good set is a cycle containing an even number of vertices.

There are a total of $$m$$ railroads in the country. Find the smallest value of $$m$$ such that no matter how the railroads are connected, given that there are a total of $$m$$ railroads, there must always exist a good set of cities.

Details and assumptions - All railroads are distinct, i.e. no two railroads connect the same pair of cities. - No railroad connects a city to itself. - This problem is not original.

×