Un hecho de problema

El problema
El problema que dio origen a la teoría de grafos era, como hemos señalado, el paseo atravesando los siete puentes sobre el río Pregel. Este río tenía una isla, isla de Kneiphof, enmedio  a la que llegaban cinco puentes, dos a cada orilla y otro que llevaba a otra isla dentro del río, que, a su vez estaba unida a las orillas por sendos puentes, tal y como indica la figura siguiente: 
El problema planteado por los paseantes de Konigsberg era el siguiente: ¿Cómo puede hacerse un paseo atravesando una sola vez cada uno de los siete puentes?. La experiencia había demostrado queera imposible hacer tal paseo, pero cuando el problema fue estudiado por Euler obtuvo una serie  de resultados que dieron luz a este problema y abrió la matemática a nuevos horizontes.
Lasimplificación de problema
Euler estaba en San Petersburgo cuando le llegó la noticia del problema de los paseantes de Konigsberg. Para resolverlo Euler trazó un esquema simplificado de la situación. La ideabásica consistió en sustituir la Tierra por puntos y los puentes por arcos.
Los puntos 1 y 3 representan las orillas del río, el punto 2 la isla Kneiphof y el punto 4 representa la otra isla. Las líneastrazadas entre los puntos son los puentes que se designan con las mismas letras con las que hemos designado los puentes en el gráfico anterior.
El problema ahora queda reducido a saber si ese gráfico,que llamaremos grafo, se puede dibujar con una línea continua, sin levantar el lápiz del papel ni “repintar” ningún arco.
Un poco de vocabulario
La gráfica anterior se llama grafo, se designa conG,  y  está formado por un número finito de puntos, llamados vértices o nodos, unidos por una serie de líneas, llamadas arcos.
Un vértice tiene grado par si en él concurren un número par de arcos.
Unvértice tiene grado impar si en él concurren un número impar de arcos.
Observación: En la gráfica anterior los vértices 1, 3 y 4 de orden tres y el 2 de orden cinco
Algunos resultados de Euler...