La isla Kueiphof en Koenigsberg (Pomerania) el río que la rodea se divide en dos brazos.

Sobre los brazos estaban construidos siete puentes y para los habitantes era motivo de distracción descubrir un itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado por los siete puentes pero pasando sólo una vez por cada uno de ellos.

Leonardo Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos. A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas.

Estudió si una figura lineal se podía dibujar con un solo trazo, sin levantar el lápiz del papel y sin pasar dos veces por el mismo sitio.

  Llegó a la siguiente conclusión:

1. Es imposible si hay más de dos vértices impares.

2. Es posible cuando:

a) Todos los vértices son pares y el punto de partida puede ser cualquiera.

b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro.

A la isla A llegan 5 puentes; a la B llegan 3 puentes; a la orilla C llegan 3 puentes y a la orilla D llegan 3 puentes, por tanto, según las conclusiones anteriores, el problema no tiene solución.

Ejemplos:

Estos dibujos pueden hacerse de un solo trazo:

Estos no pueden hacerse en las condiciones exigidas:

Este estudio de Euler dio origen a la teoría de los grafos, que se emplean en el estudio de los circuitos eléctricos, en problemas de transporte, programación con ordenador, ...