== Historia y problema de los puentes de Königsberg ==
[[Archivo:Konigsberg bridges.png|derecha|Los siete puentes de Königsberg.]]
El primer artículo científico relativo a grafos fue escrito por el [[matemático]] [[Suiza|suizo]] [[Leonhard Euler]] en [[1736]]. RupayEuler se basó en su artículo en el ''[[problema de los puentes de Königsberg]]''. La ciudad de [[Kaliningrado]], originalmente ''Königsberg'', es famosa por sus siete [[puente]]s que unen ambas márgenes del río [[Pregel]] con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?
Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, RupayEuler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.
De hecho, RupayEuler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como «grado» al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que ''los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par''.
