De zeven bruggen van Koningsbergen

De mensen die in de 18e eeuw in de stad Koningsbergen (het huidige Kaliningrad) woonden, probeerden lange tijd een puzzel op te lossen: door de stad stroomt de rivier de Pregel, die twee eilanden vormt. Over deze rivier lopen in totaal zeven bruggen naar de eilanden. Is het mogelijk om tijdens één zondagse wandeling alle bruggen over te steken, maar elke brug precies één keer? Laten we kijken hoe de bruggen over de rivier lagen:

Is het mogelijk dat we onze wandeling op een of andere plek beginnen en alle bruggen precies één keer oversteken? We kunnen het proberen: we beginnen linksonder en gaan omhoog en dan achtereenvolgens naar rechts, zo:

We zien dat we zes van de zeven bruggen hebben overgestoken, een van de bruggen hebben we gemist. We kunnen een andere route proberen…

Opnieuw hebben we maar zes van de zeven bruggen van ons Koningsbergen overgestoken. Het lijkt er bijna op dat het niet mogelijk is om met één wandeling elke brug precies één keer over te steken. Op een dag stuitte de bekende wiskundige Leonhard Euler op dit probleem. Bekend? Dat is zacht uitgedrukt: Euler was een legende van de wiskunde, naar wie zelfs het getal van Euler is genoemd. Euler nam zich voor deze puzzel te kraken. Hij begon door de afzonderlijke eilanden of delen van de stad waar bruggen naartoe en vandaan liepen, een letter te geven:

Euler maakte nu de volgende redenering: als er naar een eiland een even aantal bruggen leidt, kunnen we deze bruggen tijdens één wandeling oversteken, waar we ook beginnen. Kortom, over de ene brug komen we op het eiland aan, over de andere verlaten we het: het aantal bruggen dat we nog moeten oversteken, is met twee afgenomen. Om over de ene brug op het eiland aan te komen en over de andere te vertrekken, hebben we twee bruggen nodig. Als er zes bruggen naar een eiland leiden, bezoeken we het eiland drie keer. Stel bijvoorbeeld dat er vier bruggen naar eiland B leidden, zo:

Dan kunnen we met één zondagse wandeling alle bruggen oversteken, waar we ook beginnen. Probeer het maar! In de figuur heb ik één route aangegeven. Stel nu dat er naar eiland B nog een brug vanaf eiland D leidde:

We zien dat de route die we hebben gekozen ons niet in staat stelt alle bruggen precies één keer over te steken. We zouden over een van de bruggen terug moeten naar eiland B en dan naar eiland D moeten oversteken. Maar we kunnen een andere route kiezen. We kunnen onze wandeling op eiland B beginnen en dan kunnen we alle bruggen precies één keer oversteken:

We begonnen onze wandeling op eiland B, gingen omhoog naar gebied A, dan over de brug terug naar B, naar gebied C, dan terug naar eiland B en ten slotte naar eiland D. Als we dus beginnen op een eiland dat een oneven aantal bruggen heeft, kunnen we alle bruggen ervan precies één keer oversteken. Of we kunnen het precies andersom doen: we kunnen op eiland D beginnen en op eiland B eindigen.

Euler merkte zo op dat het, om alle bruggen precies één keer te kunnen oversteken, nodig is dat óf alle eilanden een even aantal bruggen hebben, óf dat er twee eilanden kunnen zijn die een oneven aantal bruggen hebben: op het ene eiland met een oneven aantal bruggen beginnen we en op het andere eindigen we. Alle andere eilanden moeten een even aantal bruggen hebben. Als we naar de oorspronkelijke zeven bruggen in Koningsbergen kijken:

dan zien we dat elk eiland een oneven aantal bruggen heeft! Eiland A heeft er 3, B heeft er 5, C heeft er 3 en D heeft er ook 3. Daarom heeft de puzzel geen oplossing: het is niet mogelijk om alle zeven bruggen precies één keer over te steken tijdens één zondagse wandeling. Als we een willekeurige brug zouden afbreken, zou de puzzel ineens wel een oplossing hebben. Laten we bijvoorbeeld een van de bruggen tussen de eilanden B en C afbreken:

We zien dat eiland B ineens 4 bruggen heeft en eiland C twee bruggen. Bij de eilanden A en D is het aantal bruggen niet veranderd. We hebben ineens twee eilanden met een even aantal bruggen en twee eilanden met een oneven aantal bruggen. Als we onze wandeling beginnen op een van de eilanden die een oneven aantal bruggen hebben, kunnen we alle bruggen precies één keer oversteken. In de figuur zijn we op eiland A begonnen en op eiland D geëindigd.

Leonhard Euler heeft zo een ander beroemd wiskundig probleem opgelost en min of meer de basis gelegd voor wat we tegenwoordig de grafentheorie noemen. Ter ere van hem heet in de taal van de grafentheorie een route die alle kanten precies één keer doorloopt een eulerwandeling. Komt zo'n route bovendien terug in haar beginpunt, dan heet ze een eulercykel, en een graaf met een eulercykel heet een eulergraaf.