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 tal manera que se puede llegar a cualquier ciudad desde cualquier otra ciudad. La aerolínea quiere cerrar algunos (posiblemente cero) número de vuelos, de modo que el número de vuelos necesarios para llegar a cualquier ciudad en particular desde la capital no aumente. Suponga que hay un número impar de formas en que la aerolínea puede hacer esto. Pruebe que el conjunto de ciudades se puede dividir en dos grupos, de modo que no haya ningún vuelo entre dos ciudades del mismo grupo.