6 Hay $n$ ciudades y $2$ compañías aéreas en un país. Entre cualesquiera dos ciudades hay exactamente un vuelo de $2$ vías que las conecta, operado por una de las dos compañías. Una matemática planea una ruta de viaje, de modo que comienza y termina en la misma ciudad, pasa por al menos otras dos ciudades, y cada ciudad en la ruta es visitada una vez. Ella descubre que dondequiera que comience y cualquier ruta que elija, debe tomar vuelos de ambas compañías. Halle el máximo valor de $n$.