Q9 Matemática  (Balkan MO Shortlist 2008)

Em um dos países, existem $n\ge 5$ cidades operadas por duas companhias aéreas. A cada duas cidades são operadas nos dois sentidos por no máximo uma das empresas. O governo introduziu uma restrição de que todas as viagens de ida e volta que uma empresa pode oferecer devem ter pelo menos seis cidades. Prove que não há mais de $\lfloor \frac{n^2}{3}\rfloor$ voos oferecidos por essas empresas.