3 En un país hay varias ciudades; algunas de estas ciudades están conectadas por líneas aéreas, de modo que una línea aérea conecta exactamente dos ciudades en cada caso y ambas direcciones de vuelo son posibles. Cada línea aérea pertenece a una de $k$ compañías aéreas; dos líneas aéreas de la misma compañía tienen siempre un punto final común. Demuestre que se pueden dividir todas las ciudades en $k+2$ grupos de tal manera que dos ciudades del mismo grupo nunca estén conectadas entre sí por una línea aérea.