La respuesta es negativa matematica

La respuesta es negativa, es decir, no existe una ruta con estas características. El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posiblesrecorridos existentes. Sin embargo, Euler en 1736 en su publicación «Solutio problematis ad geometriam situs pertinentis» demuestra una solución generalizada del problema, que puede aplicarse a cualquierterritorio en que ciertos accesos estén restringidos a ciertas conexiones, tales como los puentes de Königsberg. Para dicha demostración, Euler recurre a una abstracción del mapa, enfocándoseexclusivamente en las regiones terrestres y las conexiones entre ellas. Cada puente lo representó mediante una línea que unía a dos puntos, cada uno de los cuales representaba una región diferente. Así el problemase reduce a decidir si existe o no un camino que comience por uno de los puntos azules, transite por todas las líneas una única vez, y regrese al mismo punto de partida. Solución de Euler Larespuesta de Euler es extremadamente simple. Supongamos que, efectivamente, es posible realizar el dibujo sin levanter el lápiz del papel. Al realizar el dibujo, en cada vértice intermedio que atravesemosentraremos por una arista y saldremos por otra. En particular, el número de aristas que confluyen en cada vértice del grafo, exceptuando quizás los vértices inicial y final del dibujo, ha de ser par. Sillamamos "valencia" de cada vértice al número de aristas que confluyen en él, lo dicho anteriormente significa que para que el problema tenga solución es necesario que en el grafo haya como mucho dosvértices de valencia impar. En el caso del grafo de Königsberg los cuatro vértices tienen valencia impar, así que el problema no tiene solución. En realidad es fácil demostrar que la condiciónanterior es no sólo necesaria, sino también suficiente. Juntando esto con el hecho de que en todo grafo el número de aristas con valencia impar es par (porque al sumar las valencias de todos los vértices...