La teoria de grafs com es coneix avui en dia no ha aparegut fins al segle XX quan Dénes Kőnig va escriure el primer llibre que en parlava l'any 1936. Euler no parlava de grafs, ell parlava de problemes de geometria de posició. Ell va impulsar l'estudi dels grafs, però no els va inventar. El precursor de la teoria de grafs fou Leonhard Euler, que la va iniciar tot intentant resoldre el problema dels set ponts de Königsberg i el problema del cavall.

Problema dels ponts de Königsberg El problema dels ponts de Königsberg va sorgir d'una pregunta popular inofensiva. Königsberg, l'actual Kaliningrad, és una ciutat russa per la qual passa el riu Pregolya. Enmig del riu, dues grans illes estaven connectades entre elles i a les voreres mitjançant una estructura de set ponts en total. miniatura|Mapa dels ponts de Königsberg

Els habitants de la ciutat es plantejaven si era possible recórrer els set ponts de manera que només es passés per cadascun un sol cop.

Euler va resoldre aquest problema donant la primera demostració l'any 1736. Ell no va mencionar en cap moment les paraules graf, vèrtex, aresta o grau.

El primer que va fer Euler en veure aquest problema va ser pensar que realment el que deia Leibniz en el seu Geometriam situs era cert. És a dir, que existia una branca de la geometria en la qual hi havia unes propietats de posició però no propietats de distàncies. Euler no va trobar això llegint Leibniz sinó parlant amb Johann Bernoulli. Ell abans de començar va dir que semblava un problema geomètric però que no depenia de la mesura de distàncies.

A continuació Euler va descriure el problema de la següent manera.Com podem veure a la Fig. 1. Va denotar els ponts com a; a, b, c, d, e, f i g i les àrees de terra com A, B, C i D. Es va formular la pregunta; com algú pot organitzar una ruta passant una vegada per cada pont? Sense tenir en compte si acabava al mateix punt que començava. Ell va dir que primer buscaria tots els resultats i després buscaria la solució particular de començar i acabar al mateix punt. miniatura|Fig.1:Dibuix representant el que va dibuixar Euler pel problems dels ponts de Königsberg.

Va posar exemples de la notació que utilitzaria per representar els recorreguts. Per exemple AB és el pas de l'àrea de terra A a la B utilitzant qualsevol dels ponts. No obstant això, si volia especificar el pont pel qual passava l'escrivia així AbB, Recorregut de A a B passant pel pont b.

Aleshores va plantejar que un recorregut seria per exemple ABCD, començant en A, passant per B i C, per acabar en D. Ell va veure que no era una solució del problema però va deduir que la solució del problema necessitaria vuit lletres, ja que hi ha set ponts. Per tant, la solució del problema romania en trobar un recorregut de vuit lletres.

També va veure que hi havia d'haver certes restriccions en el recorregut, ja que de l'àrea de terra A a l'àrea de terra C hi havia dos ponts, per tant A i C havien de sortir correlatives dues vegades. Euler va preguntar-se si això era possible i va afirmar que si no era possible trobar un recorregut amb aquestes característiques, aleshores era impossible trobar una solució al problema perquè aquest no en tenia.

Posteriorment, va buscar un problema més senzill per trobar regles que confirmessin o no que existia aquesta seqüència de lletres. A la Fig. 2 podem veure com va plantejar un problema amb els ponts a, b, c, d, etc. amb dues àrees de terra A i B. miniatura|Fig.2:Dibuix d'un exemple proposat per Euler.

Euler va veure que si hi havia un sol pont, llavors la lletra A apareixia només una vegada sense que comencés i acabés en A, si hi havia tres ponts, llavors la lletra A apareixia dues vegades, si hi havia cinc ponts, la lletra A apareixia tres vegades. Per tant, en general, si hi ha un nombre imparell de ponts, llavors, el nombre de vegades que apareix la lletra A a la seqüència és la meitat més u del nombre de ponts.

Aplicant això al cas dels ponts de Königsberg, la lletra A hauria d'aparèixer tres vegades perquè hi ha cinc ponts fins a l'àrea A. Llavors les lletres B, C i D haurien d'aparèixer dues vegades cada una perquè hi ha tres ponts fins a cada una de les àrees. Això vol dir que el nombre de lletres de la seqüència per obtenir un resultat, si existeix, és la suma de les vegades que haurien d'aparèixer les lletres. És a dir, 3+2+2+2=9. Però només hi ha set ponts, llavors, una seqüència de lletres per la que només es passa una vegada per cada pont hauria de ser de 8 lletres. Per tant, no existeix aquesta solució.

Posteriorment, Euler intenta generalitzar aquest resultat per a qualsevol problema amb diferents nombres d'àrees i qualsevol nombre de ponts sigui parell o imparell. Ho veiem tot seguit.

Resolució als problemes tipus anterior Fins ara Euler només havia trobat solucions per a un nombre imparell de ponts. Euler va notar que si treballava amb un nombre parell de ponts les vegades que apareixia, A una àrea de terra, depenia de si el recorregut començava o no en A.

Si el recorregut començava en A i hi havia dos ponts, aleshores, A apareixia dues vegades. Però si el recorregut no començava en A i hi havia dos ponts, aleshores, A apareixia només una vegada. Va fer les comprovacions per quatre i cinc ponts obtenint resultats semblants. Generalitzant aquests casos va trobar finalment que amb un nombre parell de ponts si el recorregut començava en A, obtenia que A apareixia la meitat del nombre de ponts més u a la seqüència. En canvi si el recorregut no començava en A, obtenia exactament que A apareixia la meitat del nombre de ponts a la seqüència.

Euler va prendre un problema on apareixien aquests dos resultats a la vegada, amb nombres de ponts parells i nombres de ponts imparells, per tal de descriure un algoritme per determinar si la solució anterior existia o no. És a dir, buscava un algoritme per veure si es podia passar només una vegada per cada pont.

Com podem veure a la graella següent va fer una taula amb les àrees de terra i el nombre de ponts que sortia de cada una. Va afegir una columna amb el mínim nombre de vegades que aquella àrea de terra apareixia a la solució. Per exemple, aquest seria l'algoritme del problema dels ponts de Königsberg.

Àrees Ponts Mínim A 5 3 B 3 2 C 3 2 D 3 2 miniatura|Fig.3:Dibuix d'un altre exemple que va proposar Euler.Posava un asterisc a la lletra que tenia un nombre parell de ponts però en aquest exemple no n'hi ha cap. Va sumar els nombres de la tercera columna i es pot comprovar que la suma és més de vuit i, per tant, la solució és impossible. Euler va proposar un nou exemple, Fig. 3. Implicant dues illes A i B amb quatre rius. No estava estudiant cap lloc real, simplement feia proves imaginàries.

L'algoritme corresponent a aquest exemple és el següent.

Àrees Ponts Mínim - - 16 A* 8 4 B* 4 2 C* 4 2 D 3 2 E 5 3 F* 6 3 - - 16

Com que el nombre de la suma és setze al final de la tercera columna i no és inferior al mínim nombre necessari de lletres que trobem al principi de la columna. Euler va concloure que existia una solució. Euler aquí va confondre les condicions necessàries per les condicions suficients. Ell sense saber-ho suposava que el graf era connex.

Euler va veure que el camí o recorregut no podia començar en cap de les regions que tenia un asterisc. Per tant, no podia començar en cap àrea amb un nombre parell de ponts. Ja que si no aquell símbol havia d'aparèixer una vegada més, i la seqüència no era prou llarga. Euler va proposar la següent solució: EaFbBcFdAeFfCgAhCiDkAmEnApBoElD en aquesta notació descriu les àrees i els ponts utilitzats. La seqüència de lletres seria EFBFAFCACDAEABED.

A continuació, va fer algunes observacions més. En primer lloc, la suma dels ponts de la segona columna és el doble dels ponts totals que apareixen en el problema, ja que cada pont està comptat dues vegades. Per tant, el nombre total de ponts ha de ser parell per tant això és impossible si un nombre és imparell, o tres nombres són imparells, etc. Llavors el nombre d'àrees amb un nombre imparell de ponts ha de ser parell.

Per exemple, en el problema de Königsberg on la suma del nombre d'àrees imparelles A, B, C i F és el nombre parell quatre. I en la figura tres la suma del nombre d'àrees imparelles D i F és dos.

En segon lloc, en el cas que els nombres de la segona columna són parells, Euler va deduir que una de les lletres havia d'aparèixer tant al principi com al final del recorregut per tal que es pogués utilitzar cada una de les lletres. Euler va veure que si el problema tractés de creuar cada pont dues vegades, sempre tindria solució, ja que estaríem davant de casos on hi hauria nombres parells de ponts sempre.

També va observar que si dos dels nombres de la segona columna són imparells, llavors, el recorregut comença en una d'aquestes dues àrees amb nombre imparell de ponts i acaba a l'altre amb l'ordre adequat per tenir una successió possible de lletres. Finalment, si més de dos nombres són imparells, llavors no hi ha una seqüència amb prou lletres per creuar cada pont i el problema no té solució. Euler va enumerar aquests arguments amb una llista de tres regles, depenen de les regions amb nombres imparells de ponts:

1. Si més de dues àrees tenen un nombre de ponts senar, aleshores no existeix una seqüència de lletres que recorri tots els ponts i acabi on ha començat.

2. Si hi ha dues àrees amb nombre de ponts senar, llavors una seqüència de lletres que recorri tots els ponts existeix sempre que comenci i acabi a les dues àrees amb un nombre de ponts senar.

3. Si totes les àrees tenen un nombre de ponts parell, es pot aconseguir una seqüència de lletres que comenci i acabi a la mateixa àrea des de qualsevol àrea i recorri tots els ponts.

Finalment, Euler resol la qüestió de trobar realment el camí, un cop sap que existeix. Si dues regions estan connectades per dos o més ponts, suggereix mentalment l'eliminació d'ells, de dos en dos, i resoldre el problema utilitzant els ponts restants. Després la solució s'estén fàcilment a una solució completa.

Però aquest no va ser l'únic treball d'Euler pel que fa als grafs. També va resoldre un problema conegut com el problema del cavall. Ell el va anomenar Solution d'une question curieuse que ne paroit soumise à aucune analyse.

El problema del cavall Un dia a una empresa en la qual, amb motiu d'un joc dels escacs, alguna persona va proposar aquesta pregunta: Es pot moure un cavall (amb el seu moviment de la L) a través de totes les caselles d'un tauler d'escacs, sense haver de passar dues vegades a la mateixa casella, i començant amb un quadrat donat?

Avui en dia es coneix aquest problema com el cicle del cavall.

Euler per fer aquesta pregunta una mica més clara, va mostrar una ruta on, es començava, en una cantonada del tauler d'escacs i el cavall es mou a través de totes les places. De manera que va marcat els números per l'ordre que el cavall trepitjava cada casella. En aquest exemple de la taula, el cavall començava a la cantonada inferior esquerra, i acabava a la casella just a la dreta del punt de partida.

42 59 44 9 40 21 46 7 61 10 41 58 46 8 39 20 12 45 60 55 22 57 6 47 53 62 11 30 25 28 19 38 32 13 54 27 56 23 48 5 63 52 31 24 29 26 37 18 14 33 2 51 16 35 4 49 1 64 15 34 3 50 17 36

Euler va observar que des de la seva posició final no es podia arribar a la inicial directament. Per tant, aquest camí o recorregut segons Euler no era “reentrant” sobre si mateix. És a dir, no es podia reiterar sense passar per una casella ja utilitzada. Euler va seguir donant un exemple d'un recorregut que era “reentrant” sobre si mateix, i assenyalava que això li donava una gran quantitat de recorreguts equivalents, a partir d'aquest circuit en qualsevol casella, i seguint els números sigui cap endavant o cap enrere.

42 57 44 9 40 21 46 7 55 10 41 58 45 8 39 20 12 43 56 61 22 59 6 47 63 54 11 30 25 28 19 38 32 13 62 27 60 23 48 5 53 64 31 24 29 26 37 18 14 33 2 51 16 35 4 49 1 52 15 34 3 50 17 36