De wiskundige Euler formuleerde in 1736 het oudste grafentheoretische probleem. Het Oostpruissische Königsberg waar Euler woonde, had zeven bruggen. Euler vroeg zich af of je een stadswandeling kon maken waarbij je iedere brug precies één keer overstak en na afloop op je uitgangspunt terugkwam. Euler abstraheerde de stadsplattegrond tot een graaf, waarbij de lijnen voor bruggen stonden, en vond op die manier de voorwaarden waaronder zo'n wandeling binnen willekeurige grafen mogelijk is.
De theoretische definitie luidt: een eulerwandeling in een samenhangende graaf G is een wandeling die iedere lijn (en dus niet: ieder punt) van G precies één keer bevat. Als die wandeling gesloten is (waarbij je uitkomt op het beginpunt), spreken we van een eulertoer. Een samenhangende graaf G bevat een eulerwandeling dan en slechts dan als G hoogstens twee punten van oneven graad heeft (de graad van een punt is het aantal lijnen dat erin uitkomt). Een samenhangende graaf G heeft een eulertoer dan en slechts dan als alle punten van G even graad hebben.
In 1856 bedacht de wiskundige Hamilton een ander klassiek grafentheoretisch probleem: wanneer kun je in een graaf een rondgang maken waarbij je elk punt van de graaf precies eenmaal aandoet? Een praktische versie hiervan is het 'handelsreizigerprobleem': een man wil vanuit zijn woonplaats A. een aantal plaatsen bezoeken en dan terugkeren naar A. Kan hij een reisschema opstellen waarbij hij elke plaats maar eenmaal bezoekt?
Rook
Zo'n rondgang heet sindsdien een hamiltoncykel: een cykel die alle punten (dus niet: lijnen) van een graaf G bevat. Begin- en eindpunt zijn daarbij gelijk. Het lastige van hamiltoncykels is dat er geen methode bekend is waarmee je net zo eenvoudig kunt nagaan of een gegeven graaf een hamiltoncykel heeft als dat mogelijk is voor een eulertoer.
'Het lijkt hetzelfde als een eulertoer', legt Veldman uit, 'maar nagaan of een gegeven graaf een hamiltoncykel heeft is veel moeilijker. Daar is nog geen goede en snelle werkwijze voor ontwikkeld. Een computer kan zo'n hamiltoncykel dan ook niet snel vinden. Als je het voor grote grafen toch probeert, komt er na een tijdje gegarandeerd rook uit de computer.'
Broersma en Veldman zoeken al jaren naar voorwaarden waaronder een graaf een hamiltoncykel bevat. Een ongestructureerd idee is vanouds dat als er in een graaf maar voldoende lijnen zijn, er vast wel zo'n cykel is.
Een meer gestructureerde aanpak gaat uit van de samenhang van een graaf, uitgedrukt in het minimaal aantal punten dat je weg moet halen om de samenhang in de graaf te verbreken (zodat je niet meer van elk punt naar elk ander punt kunt gaan). Broersma: 'Je zou denken: als de samenhang maar groot genoeg is, is er vast wel een hamiltoncykel. Dat is niet zo.'
Taaiheid
Een nog verfijndere maat voor samenhang is taaiheid ('toughness'). Deze maat houdt niet alleen rekening met het aantal punten dat je weg moet latenom de samenhang te verbreken, maar ook met het aantal componenten dat vervolgens ontstaat. De taaiheid van een graaf G is dan het minimum van het aantal punten van de graaf dat je weg haalt om de samenhang te verbreken, gedeeld door het aantal componenten dat zo ontstaat.
Als een graaf G een hamiltoncykel heeft, dan is die graaf 1-taai (met andere woorden: de taaiheid is groter dan of gelijk aan 1). De Tsjechisch-Amerikaanse wiskundige V. Chvátal opperde in een artikel uit 1973 echter het vermoeden dat als omgekeerd een graaf 2-taai is, er een hamiltoncykel in de graaf zal bestaan. Deze suggestie groeide sinds 1973 uit tot een geruchtmakende hersenkraker in de hamiltonse grafentheorie.
Twee weken geleden werd de ban gebroken. Broersma en Veldman wisten, samen met hun Amerikaanse gast Doug Bauer (Stevens Institute of Technology, Hoboken New Jersey), aan te tonen dat de bijna vijfentwintig jaar oude gedachte van Chvátal niet klopt. 'Wij hebben oneindig veel grafen gevonden die 2-taai zijn maar géén hamiltoncykel bevatten', melden ze trots.
Het probleem houdt het tweetal al bezig sinds 1995, toen mondiale grafen-experts zich er tijdens een workshop in Twente een week lang vergeefs over bogen. Broersma: 'Ik heb altijd al gedacht dat het vermoeden van Chvátal onjuist was, en dat groeide bijna uit tot een frustratie.'
Tijdens de Twente Workshop on Graphs and Combinatorial Optimization piekerden een groot aantal wiskundigen vorige maand opnieuw over het vraagstuk. Na afloop van de voordrachten bleven Broersma en Veldman met collega's nog urenlang 'brainstormen'. Toen begon de TW'ers langzaam te dagen welk type grafen 2-taai waren zonder een hamiltoncykel te bevatten.
Opwinding
Geagiteerd puzzelde Veldman thuis tot drie uur 's nachts door. Broersma schoot 's nachts om vijf uur wakker en werkte meteen een artikel uit. Onafhankelijk van elkaar schreven ze de bewijsvoering uit. De volgende ochtend vergeleken en controleerden ze hun werk. Het klopte.
Grote opwinding dus bij TW. Veel collega's kwamen langs om de grafen van Broersma en Veldman te bewonderen. Broersma: 'Zo heel moeilijk was het achteraf niet eens, maar in eerste instantie durfden we het zelf amper te geloven. We hebben het keer op keer opnieuw gecontroleerd.'
Het is alsof een droom uiteen is gespat, mijmeren de twee TW'ers. 'We hebben Chvátals mooie vermoeden dat, als het waar was geweest, een unificerende theoretische werking zou hebben gehad, voorgoed gefalsifieerd. In zekere zin zijn we dus weer terug bij af.'
Voor wiskundigen is dit een 'echte kick'. 'We lopen al dagen euforisch rond', glimmen Broersma en Veldman. Het bewijs op zich mag eenvoudig zijn, het vinden ervan was dat beslist niet. 'Het is allemaal gebaseerd op redenering, niet op rekenkracht. Met de computer zul je zo'n graaf nooit vinden, want hij heeft minstens veertig punten en daar komt de computer niet uit.' Maar ze blijven bescheiden. Veldman: 'Je hebt wel een dosis geluk nodig, want in elke doorbraak zit ook een toevalselement.'
Het artikel van Broersma en Veldman ligt inmiddels uitgetikt klaar. Het wordt gepubliceerd in de 'proceedings' van de Twentse workshop. 'Maar het nieuws gaat al als een lopend vuurtje rond.' Broersma en Veldman zullen Chvátal beslist een briefje sturen om te melden dat ze zijn vermoeden hebben weerlegd. Ze denken niet dat het hem erg zal spijten. 'Een mooie weerlegging spreekt iedere wiskundige aan.'
