Prueba : no se puede dibujar esta figura sin levantar el bolígrafo

Question

Esta pregunta puede resultar ridícula, pero siempre me ha parecido interesante... Aquí está : (No puedo poner imagen así que os pongo el enlace de las fotos) Cuando estaba en la escuela solía dibujar casas cuando me aburría :

Se puede dibujar sin levantar el bolígrafo. Pero luego traté de dibujar dos casas de lado a lado :

Entonces me di cuenta de que en realidad no se puede hacer sin levantar el bolígrafo. Lo intenté de todas las maneras posibles. Al final siempre falta una línea.

Por eso me preguntaba si existía alguna prueba de que realmente no puedo hacerlo.

He oído que hay que contar el número total de líneas y el número de intersecciones y que este número nos dice algo, pero no estoy nada seguro.

Soy estudiante de primer curso de matemáticas, así que aún no he estudiado teoría de grafos.

Gracias.

Answer 1

Me parece una buena excusa para estudiar (sólo un poco) teoría de grafos. Echa un vistazo a las conclusiones de Euler en este famoso problema . Debería decirte todo lo que necesitas saber (y más). En particular, la segunda figura tiene $4$ nodos de grado impar (es decir, un número impar de segmentos que tienen ese punto final común) --las esquinas exteriores inferiores y los dos nodos donde se juntan las "casas"-- por lo que no se puede trazar sin levantar la pluma o desandar al menos un segmento del camino.

Answer 2

Tomemos un vértice con tres aristas. Supongamos que NO empieza ahí. Entonces hay una primera vez que llegarás a este vértice, a través de uno de los posibles caminos que conducen a él. No será el final de tu dibujo porque aún no se han recorrido otros dos caminos. Así, saldrás de este vértice, a través de un segundo camino adyacente. Como resultado, cuando recorras el tercer camino en algún momento, no podrás salir de este vértice porque no habrá caminos no recorridos disponibles. En otras palabras, tu dibujo tendrá que terminar aquí.

Por lo tanto, hemos demostrado que si no se empieza en un vértice (con impar número de aristas), tendrá que terminar allí.

Lo mismo ocurre con los vértices con 5 aristas. Por tanto, si un grafo tiene más de dos vértices con grados Impares, no podrás dibujarlo.