De syv broer i Königsberg: Eulers bevis og grafteoriens begyndelse

For det første påpegede Euler, at valget af rute inden for hver landmasse er ligegyldigt. Den eneste vigtige egenskab ved en rute er den rækkefølge, i hvilken broerne krydses. Så han ændrede problemet til abstrakte termer. Dette lagde grunden til grafteori. Han fjernede alle funktioner undtagen listen over landmasser og broerne, der forbinder dem. I grafteoriens sprog erstattede han hver landmasse med et abstrakt "toppunkt" eller knudepunkt. Derefter erstattede han hver bro med en abstrakt forbindelse, en "kant". En kant (vej) registrerede, hvilke to hjørner (landmasser) der var forbundet. På denne måde dannede han en graf.

→ →

Den tegnede graf er et abstrakt billede af problemet. Kanterne kan derfor forbindes på en hvilken som helst måde. Det er kun vigtigt, om to punkter er forbundet eller ej. Hvis man ændrer billedet af grafen, ændrer man ikke selve grafen.

Dernæst bemærkede Euler, at når man kommer ind i et toppunkt via en bro, så forlader man også toppunktet via en bro (undtagen ved enderne af vandringen). I en hvilken som helst tur i grafen er antallet af gange, man kommer ind i et toppunkt, lig med antallet af gange, man forlader det. Hvis hver bro er blevet passeret præcis én gang, følger det, at for hver landmasse (bortset fra dem, der er valgt som start- og målpunkt), skal antallet af broer, der berører den pågældende landmasse, være lige. Det skyldes, at hvis der er n broer, er den krydset præcis 2n gange. Alle fire landmasser i det oprindelige problem er imidlertid berørt af et ulige antal broer (den ene er berørt af 5 broer, og hver af de tre andre er berørt af 3). Der er højst to masser, som kan være slutpunkter for en vandring. Så forslaget om, at en vandring skal krydse hver bro én gang, fører til en selvmodsigelse.

I moderne sprogbrug viser Euler, at det afhænger af knudernes grader, om det er muligt at gå gennem en graf, hvor hver kant krydses én gang eller ej. Graden af en knude er antallet af kanter, der berører den. Euler viser, at en nødvendig betingelse for at gå gennem grafen er, at den er forbundet og har præcis nul eller to knuder af ulige grad. Dette resultat, som Euler har fremlagt, blev senere bevist af Carl Hierholzer. En sådan vandring kaldes nu en Euler-sti eller Euler-gang. Hvis der er knuder af ulige grad, vil enhver eulersk sti starte ved den ene af dem og slutte ved den anden. Da grafen, der repræsenterer det historiske Königsberg, har fire knuder af ulige grad, kan den ikke have en eulersk sti.

Eulers arbejde blev præsenteret for Sankt Petersborg Akademiet den 26. august 1735. Det blev offentliggjort som Solutio problematis ad geometriam situs pertinentis (Løsningen af et problem vedrørende geometrien af positionen) i tidsskriftet Commentarii academiae scientiarum Petropolitanae i 1741. Den er tilgængelig på engelsk i The World of Mathematics.

I matematikkens historie anses Eulers løsning af Königsberg-broproblemet for at være den første sætning i grafteori. Grafteori er et emne, der nu generelt betragtes som en gren af kombinatorikken.

To af de syv oprindelige broer blev ødelagt under bombningen af Königsberg under Anden Verdenskrig. To andre blev senere revet ned. De blev erstattet af en moderne motorvej. De tre andre broer er bevaret, selv om kun to af dem er fra Eulers tid (den ene blev genopbygget i 1935). I 2000 var der således fem broer i Kaliningrad.

I grafteori har to af knuderne nu grad 2, og de to andre har grad 3. Derfor er en eulersk sti nu mulig, men da den skal begynde på den ene ø og slutte på den anden ø, er den upraktisk for turister.

• Icosian spil
• Hamilton-bane
• Vand, gas og elektricitet
• Rejsende sælger-problem