2019 metro stations, create k more lines
Source: St. Petersburg 2019 9.2
May 2, 2019
combinatorics
Problem Statement
In the city built are metro stations. Some pairs of stations are connected. tunnels, and from any station through the tunnels you can reach any other. The mayor ordered to organize several metro lines: each line should include several different stations connected in series by tunnels (several lines can pass through the same tunnel), and in each station must lie at least on one line. To save money no more than lines should be made. It turned out that the order of the mayor is not feasible. What is the largest it could to happen?