Viajar al punto de origen sin utilizar dos veces la misma carretera

Question

BdMO 2013 Secundaria:

Existen $n$ ciudades de un país. Entre dos ciudades cualesquiera hay como máximo una carretera. Supongamos que el número total de carreteras es $n$ . Demostrar que existe una ciudad tal que partiendo de ella es posible volver a ella sin recorrer nunca recorrer dos veces el mismo camino.

Siento que debería estar usando el Principio del Casillero en alguna parte. Comprobamos si hay $n=2$ Sin embargo, para $n=2$ sólo hay $2$ ciudades y sólo $1$ Por lo tanto,n no puede ser igual a $2$ . $n=3$ y todo lo que sea mayor que $3$ También es importante señalar que cuando $n>3$ existe al menos $2$ ciudades que no están conectadas entre sí.Sin embargo, $n$ número de ciudades implica $\dbinom{n}{2}$ número de carreteras.Pero sigo sin poder deducir ninguna información útil de mis observaciones.Se agradecerá cualquier pista.

Answer 1

Supongamos que la afirmación es cierta para $S(n)$ . Intentemos demostrar que la afirmación es válida para $S(n+1)$ añadiendo una ciudad C.

Si C no tiene ninguna carretera que la conecte, entonces podemos eliminar C y cualquier carretera aleatoria del grafo y seguiremos teniendo una solución mediante $S(n)$ . Del mismo modo, si C sólo tiene una carretera que la conecta con alguna otra ciudad, la misma lógica da como resultado una solución tras eliminar C y su carretera.

Supongamos ahora que C tiene dos carreteras que la conectan con las ciudades A y B. Si A y B están conectadas directamente, tenemos un ciclo en ABC. De lo contrario, podemos imaginar C y sus carreteras como una carretera que conecta estas A y B, por lo que de nuevo tenemos por $S(n)$ una solución.

Por último, si C está conectado por $3$ o más carreteras a diferentes ciudades, debemos tener al menos una ciudad (digamos D) en el país conectada a una carretera como máximo. (Esto se debe a que si cada ciudad distinta de C tiene dos o más carreteras, debemos tener $\ge \frac{2n+3}{2} > n+1$ carreteras). Quite la ciudad D y cualquier carretera conectada a ella (o una carretera aleatoria si D no está conectada) y debemos tener una solución de nuevo por $S(n)$ .

Como ha demostrado $S(3)$ y el resto se deduce por inducción.