De sju broene i Königsberg

Folk som bodde i byen Königsberg på 1700-tallet, grublet lenge over en gåte: Elven Pregolja renner gjennom byen og danner to øyer. Til sammen sju broer fører over elven og ut til øyene. Er det mulig å gå over alle broene på én søndagstur, men over hver bro nøyaktig én gang? La oss se hvordan broene lå over elven:

Er det mulig å begynne turen på et sted og gå over alle broene nøyaktig én gang? Vi kan prøve. Vi begynner nede til venstre og går oppover og deretter etter hvert mot høyre, slik:

Vi ser at vi har gått over seks av sju broer, og én av broene gikk vi forbi. Vi kan prøve en annen rute…

Igjen gikk vi over bare seks av de sju broene i Königsberg. Det ser nesten ut til at det ikke er mulig å gå over hver bro nøyaktig én gang på én tur. En dag støtte den berømte matematikeren Leonhard Euler på dette problemet. Berømt og berømt — Euler var en ren legende i matematikken, og etter ham er selve Eulers tall oppkalt. Euler bestemte seg for å knekke denne gåten. Han begynte med å gi navn til de enkelte øyene eller delene av byen som broene førte til og fra:

Euler gjorde nå følgende overveielse: Hvis et like antall broer fører til en øy, kan vi gå over alle disse broene på én tur, uansett hvor vi begynner. Rett og slett, over én bro kommer vi til øya, over en annen drar vi derfra — antallet broer som gjenstår å gå over, har blitt to færre. For å kunne komme til øya over én bro og dra derfra over en annen trenger vi to broer. Hvis seks broer fører til en øy, besøker vi øya tre ganger. La oss for eksempel tenke oss at fire broer førte til øy B slik:

Da kan vi gå over alle broene på én søndagstur, uansett hvor vi begynner. Prøv selv! På figuren har jeg markert én rute. La oss tenke oss at det i tillegg førte en bro til øy B fra øy D:

Vi ser at ruten vi valgte, ikke lar oss gå over alle broene nøyaktig én gang. Vi måtte ha gått tilbake til øy B over en av broene og så gått videre til øy D. Men vi kan velge en annen rute. Vi kan begynne turen på øy B, og da kan vi gå over alle broene nøyaktig én gang:

Vi begynte turen på øy B, gikk opp til område A, så over broen tilbake til B, til område C, så tilbake til øy B og til slutt til øy D. Hvis vi begynner på en øy som har et odde antall broer, kan vi altså gå over alle broene som fører dit, nøyaktig én gang. Eller vi kan gå helt motsatt vei — vi kan begynne på øy D og slutte på øy B.

Euler la dermed merke til at for at det skal være mulig å gå over alle broene nøyaktig én gang, må det gjelde at enten må alle øyene ha et like antall broer, eller så kan det være to øyer som har et odde antall broer — på den ene øya med et odde antall broer begynner vi, og på den andre slutter vi. Alle de andre øyene må ha et like antall broer. Hvis vi ser på de opprinnelige sju broene i Königsberg:

ser vi at hver øy har et odde antall broer! Øy A har 3, B har 5, C har 3 og D har også 3. Derfor har gåten ingen løsning — det er ikke mulig å gå over alle de sju broene nøyaktig én gang på én søndagstur. Hvis vi rev en hvilken som helst av broene, ville gåten plutselig fått en løsning. La oss for eksempel rive én av broene mellom øy B og C:

Vi ser at øy B med ett nå har 4 broer og øy C to broer. Antallet broer til øyene A og D har ikke endret seg. Vi har plutselig to øyer med et like antall broer og to øyer med et odde antall broer. Hvis vi begynner turen på en av øyene som har et odde antall broer, klarer vi å gå over alle broene nøyaktig én gang. På figuren begynte vi på øy A og sluttet på øy D.

Leonhard Euler løste dermed enda et berømt matematisk problem og la mer eller mindre grunnlaget for det vi i dag kaller grafteori, og til hans ære kalles en graf der vi kan gå gjennom alle kantene nøyaktig én gang, en Eulergraf i grafteoriens språk.