Le linee aeree dell.Aeristan

Consideriamo un grafo con le 15 città e le rotte delle tre compagnie aeree a, b e c indicate da una linea intera, una tratteggiata e una puntinata. Perché il grafo delle città resti comunque connesso se una delle compagnie viene tolta, ogni coppia di compagnie deve avere almeno 14 rotte; pertanto a+b ≥ 14, a+c ≥ 14, b+c ≥ 14. Sommando le tre disuguaglianze otteniamo che il numero totale di rotte deve essere almeno pari a 21. Un modo per avere esattamente 21 rotte è mostrato nella figura qui sotto: un hub usato da una delle compagnie, e sette connessioni punto-punto tra le città servite dalle altre due.

Un'ultima parola

Questa struttura è anche chiamata "il grafo dell'amicizia" perché se i nodi rappresentano persone e gli archi relazioni di amicizia, qualunque coppia di persone ha esattamente un amico in comune. Se il numero di nodi fosse pari, la cosa sarebbe impossibile.