Megoldás: 3.4
Az ottani megoldást elmondhatjuk a ,,szélességi faváz" nyelvén is. A városok a gráf pontjai, a járatok az élek.
Vesszük a gráf egy
x pontjából induló szélességi favázát, ennek két emelete van, az elsőn legfeljebb három pont van, a másodikon legfeljebb hat. A gráfnak tehát maximálisan 10 pontja lehet. Az is csak úgy, hogy az
x-szel összekötött pontok között nem fut él. Mivel
x tetszőleges, ez azt jelenti, hogy a gráfban nincs háromszög. Másrészt
x semelyik két szomszédjának sem lehet közös szomszédja
x-en kívül, különben a második emeletre kevesebb pont jutna. Tehát a gráfban nincs
C4
sem.
A második emeleten levő hat pont egy 2-reguláris gráfot feszít, amelyben nincs háromszög. Egyetlen ilyen gráf van: a
C6
. Tudjuk még, hogy ennek éleit úgy kell behúznunk, hogy egyetlen pont se legyen szomszédos két olyan ponttal, amelyek ugyanannak az első emeleti pontnak a gyerekei. Ezt figyelembe véve a második emelet pontjai között futó élek izomorfiától eltekintve csak egyféleképp húzhatók be. A kapott gráf megfelel a feltételeknek, ugyanis nincs benne sem háromszög, sem
C4
, így bármely pontjából induló szélességi faváza kétemeletes, tehát két átszállással bármely pontból bármely pontba eljuthatunk.