Le linee aeree dell.Aeristan

La nazione dell'Aeristan ha quindici aeroporti, uno per ciascuna delle maggiori città del paese, e tre compagnie aeree la cui flotta unisce coppie di città. Qual è il numero minimo di rotte possibile per cui, anche se una delle compagnie fallisse, sarebbe comunque possibile andare da una qualunque città a una qualunque altra città, al limite facendo uno o più scali e cambiando aereo?

   

   

Problema tratto da Peter Winkler, Mathematical Puzzles, "Air Routes in Aerostan"; immagine di GDJ, da OpenClipart.org.