There are $2^{2n+1}$ towns with $2n+1$ companies and each two towns are connected with airlines from one of the companies. What’s the greatest number $k$ with the following property: We can close $k$ of the companies and their airlines in such way that we can still reach each town from any other (connected graph).
Problem
Source: VII International Festival of Young Mathematicians Sozopol 2016, Theme for 10-12 grade
Tags: combinatorics, graph