Königsbergs sju broar

För det första påpekade Euler att valet av rutt inom varje landmassa inte spelar någon roll. Den enda viktiga egenskapen hos en rutt är i vilken ordning broarna passeras. Så han ändrade problemet till abstrakta termer. Detta lade grunden till grafteorin. Han tog bort alla egenskaper utom förteckningen över landmassor och broarna som förbinder dem. På grafteorins språk ersatte han varje landmassa med en abstrakt "vertex" eller nod. Sedan ersatte han varje bro med en abstrakt förbindelse, en "kant". En kant (väg) angav vilka två hörn (landmassor) som var förbundna. På detta sätt bildade han en graf.

→ →

Grafen är en abstrakt bild av problemet. Kanterna kan alltså sammanfogas på vilket sätt som helst. Det är bara om två punkter är sammanlänkade eller inte som är viktigt. Att ändra bilden av grafen ändrar inte själva grafen.

Därefter observerade Euler att när man kommer in i ett hörn genom en bro, lämnar man hörnet genom en bro (utom vid slutpunkterna av vandringen). I varje promenad i grafen är antalet gånger man kommer in i en topp lika med antalet gånger man lämnar den. Om varje bro har korsats exakt en gång, följer att för varje landmassa (utom de som valts för start och mål) måste antalet broar som rör den landmassan vara jämnt. Detta beror på att om det finns n broar, korsas den exakt 2n gånger. Alla fyra landmassorna i det ursprungliga problemet berörs dock av ett udda antal broar (en av dem berörs av 5 broar och var och en av de tre andra berörs av 3 broar). Det finns högst två landmassor som kan vara slutpunkter för en vandring. Så påståendet om att en promenad passerar varje bro en gång leder till en motsägelse.

På modernt språk visar Euler att om det är möjligt att gå genom en graf och korsa varje kant en gång eller inte beror på nodernas grader. Graden av en nod är antalet kanter som berör den. Euler visar att ett nödvändigt villkor för vandringen är att grafen är ansluten och har exakt noll eller två noder av udda grad. Eulers resultat bevisades senare av Carl Hierholzer. En sådan vandring kallas nu för en eulersk väg eller Eulers vandring. Om det finns noder av udda grad kommer varje eulerskt spår att börja vid en av dem och sluta vid den andra. Eftersom grafen som representerar det historiska Königsberg har fyra noder av udda grad kan den inte ha en eulersk väg.

Eulers arbete presenterades för S:t Petersburgs akademi den 26 augusti 1735. Det publicerades som Solutio problematis ad geometriam situs pertinentis (Lösningen på ett problem som rör geometrin för positionen) i tidskriften Commentarii academiae scientiarum Petropolitanae 1741. Den finns tillgänglig på engelska i The World of Mathematics.

I matematikens historia anses Eulers lösning på problemet med Königsbergsbron vara grafteorins första sats. Grafteori är ett ämne som numera allmänt betraktas som en gren av kombinatoriken.

Två av de sju ursprungliga broarna förstördes vid bombningen av Königsberg under andra världskriget. Två andra revs senare. De ersattes av en modern motorväg. De tre andra broarna finns kvar, även om endast två av dem är från Eulers tid (en av dem byggdes om 1935). År 2000 fanns det således fem broar i Kaliningrad.

Enligt grafteorin har två av noderna nu grad 2 och de andra två har grad 3. Därför är en eulersk väg nu möjlig, men eftersom den måste börja på den ena ön och sluta på den andra är den opraktisk för turister.

• Icosiskt spel
• Hamiltons väg
• Vatten, gas och elektricitet
• Problemet med resande försäljare