bijna triviaal ondertss

In een land met $n$ grote steden en $2$ luchtvaartmaatschappijen, is ieder paar steden verbonden met een heen- en weervlucht georganiseerd door $1$ maatschappij.
Men wil een ritje maken, zodat men enkele steden $(\ge 2)$ exact een keer bezoekt en terug eindigt in het startpunt. Het blijkt dat hiervoor bij beide maatschappijen tickets gekocht moeten worden gekocht. Wat is de maximale $n$ die mogelijk is?