16 Hay $n$ ciudades en un país, una de las cuales es la capital. Una aerolínea opera vuelos bidireccionales entre algunos pares de ciudades de modo que se puede llegar de cualquier ciudad a cualquier otra. La aerolínea quiere cancelar algunos vuelos (posiblemente ninguno), de modo que el número de vuelos necesarios para llegar desde la capital a cualquier ciudad en particular no aumente. Suponga que hay un número impar de maneras en que la aerolínea puede hacer esto. Demuestre que el conjunto de ciudades puede dividirse en dos grupos, de modo que no haya vuelo entre dos ciudades del mismo grupo. Propuesto por Pranjal Srivastava Rijul