The classics are back
Source: All-Russian 2021/10.3
April 19, 2021
combinatoricsgraph theory
Problem Statement
In the country there're cities and some pairs of cities are connected by two-way airlines (each pair with no more than one). Every airline belongs to one of companies. It turns out that it's possible to get to any city from any other, but it fails when we delete all airlines belonging to any one of the companies. What is the maximum possible number of airlines in the country ?