Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Procedamos por inducción sobre $n$. El caso base es $n=2$, en cuyo caso hay necesariamente dos puntos unidos por $n-1=1$ segmentos y no hay nada que probar. Supongamos entonces que el enunciado es cierto tal cual está escrito para $n$ puntos y veamos lo que pasa si tenemos $n+1$ puntos con dicha propiedad. Al hacer un camino a lo largo de los segmentos sin repetir segmento, como no podemos volver a ningún punto ya visitado (habría dos caminos distintos con el mismo origen y el mismo final), llegará un momento en que no podremos seguir y habremos alcanzado un punto $p_0$ al que solo llega un segmento (mediante el cual hemos accedido a $p_0$). Si eliminamos $p_0$ y dicho segmento, tendremos $n$ puntos que verifican la misma propiedad, luego la hipótesis de inducción nos asegura que el número de segmentos es $n-1$. Añadiendo el que hemos eliminado, deducimos que el número de segmentos para $n+1$ puntos es $n$, como queríamos probar.