L'any 1254 l'Orde dels Cavallers Teutons va fundar la ciutat de Königsberg, que literalment es tradueix com "La muntanya del rei". Degut a la seva bona posició estratègica sobre el riu Pregel, va esdevenir un punt d'intercanvi i important ciutat medieval. El riu dividia la ciutat en 4 regions connectades per 7 ponts: el Pont de Blacksmith, el Pont Enllaç, el Pont Alt, el Pont Verd, el Pont de Mel, el Pont del Comerciant i el Pont de Llana.

Es diu que els habitants de Königsberg passaven les tardes de Diumenge passejant per la ciutat. El problema que els mateixos ciutadants es van plantejar és si era possible creuar exactament una vegada per tots i cada un dels ponts.

El 1727 Leonhard Euler treballava per l'Acadèmia de Ciències de Sant Petersburg. El 1736 Euler va escriure la solució en un article amb el títol 'Solutio problematis ad geometriam situs pertinentis'

Tot i que no està clar com Euler va arribar a conéixer aquest problema, s'han trobat un seguit de cartes que s'escrivia amb Carl Leonhard Gottlieb Ehler, alcalde de Danzig, a 80 milles de Königsberg, on es parlava d'aquest problema.

El mateix Euler, en una carta a un matemàtic italià, el 13 de Març de 1736, escriu:

M'han proposat un problema sobre l'illa de la ciutat de Königsberg, envoltada per un riu travessat per 7 ponts, i se m'ha plantejat si algú podia travessar els ponts en un camí que els enllaci de tal manera que cada pont només sigui creuat una vegada.

Euler, en la mateixa carta, considera que la qüestió és "banal", però la considera d'interés pel fet que no es pot resoldre ni amb geometria, ni algebra ni amb l'art de comptar. Associa el problema a la geometria de posició, introduïda per Leibniz recentment.

En l'article de 1736 Euler descriu el problema, resol el cas particular de Königsberg i finalment, generalitza el problema. Euler es pregunta:

Sigui quina sigui la distribució i divisió del riu en branques i el número de ponts que el trevessen, es pot saber si és possible creuar tots els ponts exactament una vegada?

Tot i que es pot anar provant totes les possibilitats, Euler ho descarta, ja que seria pesat de fer i impossible si hi hagués més ponts i illes.

Euler usa les lletres en majúscula A, B, C i D per referir-se a les illes i les lletres en minúscula a, b, c, d, e, f i g per referir-se als ponts. Si un caminant va des de A a B pel pont a o b, ho escriu AB - on la primera lletra representa la regió d'on surt el caminant i la segona lletra, la regió cap a on es dirigeix.

D'aquesta manera, si un camí consta de n lletres, per tal que tingui solució, cal que estigui unit per n-1 ponts. En el cas dels ponts de Königsberg, el problema té 7 ponts i, per tant, requereix d'un camí de 8 lletres (que es poden repetir).

Quina és la relació entre el número de ponts que uneixen dues regions amb el número de lletres corresponents a aquest camí? Mirem l'exemple senzill proposat per Euler:

En el cas anterior la seqüència començant per A és:

AaBbAcBdAeBfA

o bé, ometent els ponts:

AB-BA-AB-BA-AB-BA

Euler dedueix que si el nombre de ponts és imparell, aleshores el nombre de lletres A que hi ha d’haver a la seqüència seria la meitat d’aquest nombre de ponts més un i si el nombre de ponts és parell és directament la meitat.

Amb això és suficient per determinar la impossibilitat del camí buscat. Una de les illes, A, està connectada per 5 ponts; per tant, el camí ha de contenir 3 lletres A. De manera similar, ha d'haver 2 lletres B, 2 lletres C i 2 lletres C.

Regió	A	B	C	D
Ponts	5	3	3	3
Freqüència	3	2	2	2

Sumant la fila de freqüències de totes les lletres, que representen les repeticions de cada lletra en el camí, veiem que faria falta 9 lletres, però el camí usant 7 ponts només en necessita 8. Per tant, no existeix el camí que busquem.

Generalitzant, la freqüència de cada lletra depenent del nombre de ponts, si aquest és imparell és . Si és parell és o si comença per aquesta regió.

Podem escriure la taula de freqüències en aquest cas, marcant amb un asterisc les illes amb un nombre senar de ponts

Regió	A	B	C	D*	E*	F
Ponts	8	4	4	3	5	6
Freqüència	4	2	2	2	3	3

Si la suma de freqüències és el nombre de lletres necessaries menys u, donat el nombre de ponts, el camí que busquem existirà. En aquest cas, la fila de freqüències suma 16, que és exactament el nombre de lletres necessaries per un camí amb 15 ponts, tal com és. Euler va mostrar un possible camí:

EaFbBcFdAeFfCgAhCiDkAmEnApBoElD

Aquest tipus de problemes es poden resoldre molt més fàcilment si ho representem en forma de graf, tal com es va començar a fer a partir del segle XIX. L'objectiu és determinar si una figura es pot dibuixar sense aixecar el llapis i sense repetir cap aresta (Camí Eulerià). Podem transformar els dibuixos que hem vist en grafs:

• Si hi ha més de dos nodes amb grau senar, aleshores el camí Eulerià no és possible

• Si hi ha exactament dos nodes amb grau senar, aleshores el camí Eulerià existeix si comença en un dels dos nodes

• Si no hi ha cap node amb grau senar, el camí Eulerià existeix començant per qualsevol node.

ACTUALITAT