Page 69 - 22 Euler

Así pues, lo deducido por Euler puede escribirse así:

Llamemos n al número de nodos de grado impar.

a) sin= O el grafo contiene al menos un circuito euleriano.

b) Sin= 2 hay al menos un camino euleriano pero no un circuito.

c) Si n > 2 no hay ni camino ni circuito.

Dado que, en el caso que nos ocupa, n = 4, los paseantes de
Kónigsberg se quedaron sin «paseo perfecto». Si le hubiesen pre-
guntado a Euler, les podría haber dicho que la adición o supresión
de un simple puente habría hecho su problema resoluble.

UN PROBLEMA RELACIONADO: EL PASEO DEL CABA LLO

Otra cuestión también estudiada por Euler y que de algún modo
se rel~ciona con él tema de los grafos es el problema de ajedrez
del paseo del caballo, abordado en
1759 en Solution d'une question
curieuse que ne paróit soumise FIG. 4
a aucun analyse (Solución a una
cuestión curiosa que no parece
sujeta a ningún análisis). El pro-
blema consistía en, partiendo de
cualquier punto del tablero de aje-
drez, conseguir un recorrido para
el caballo de manera que pisara
todas las casillas. Euler encontró la
solución, poniendo de paso el fun-
damento a los posteriormente de-
nominados grafos hamiltonianos,
que presentan cantinas que pasan
una sola vez por cada vértice y vuel-
ven al punto de partida (figura 4).

S: Rl::S, CONSTANTES Y FUNCIONES: EULER EN RUSIA 69