Team Selection Test for IMO 2007

Using the inclusion-exclusion principle we find that the number of ways the flights can be arranged so that each city is connected to at least one other city by a flight is $$2^{\left(\frac{6}{2}\right)}-\left(\genfrac{}{}{0ex}{}{6}{1}\right)2^{\left(\frac{5}{2}\right)}+\left(\genfrac{}{}{0ex}{}{6}{2}\right)2^{\left(\frac{4}{2}\right)}-\left(\genfrac{}{}{0ex}{}{6}{3}\right)2^{\left(\frac{3}{2}\right)}+\left(\genfrac{}{}{0ex}{}{6}{4}\right)2^{\left(\frac{2}{2}\right)}-\left(\genfrac{}{}{0ex}{}{6}{5}\right)+\left(\genfrac{}{}{0ex}{}{6}{6}\right)=27449.$$ Among these, the configurations that do not satisfy the condition of the problem, and the corresponding number of ways the flights can be arranged are shown in the following figure: Therefore, the answer is $27449-745=26704$.