Bewijs omtrent een gesloten wandeling in een samenhangende graaf
Ik moet de volgende stelling bewijzen: Zij G een samenhangende graaf zonder punten van graad één. Dan bestaat in G een gesloten wandeling waarin elke lijn precies tweemaal voorkomt, maar geen twee opeenvolgende lijnen aan elkaar gelijk zijn. Kunnen jullie me hiermee helpen?
maikel
Student universiteit - dinsdag 4 mei 2004
Antwoord
Dag Maikel,
Ik denk een bewijs gevonden te hebben dat in twee delen gaat: eerst bewijs ik dat er een gesloten wandeling bestaat die elke boog tweemaal aandoet. Daarna bewijs ik dat, als de graad overal minstens twee is, je een wandeling kan vinden zonder herhalingen.
1. Er bestaat een gesloten wandeling. Bewijs: elke samenhangende graaf bevat een samenhangende opspannende boom (dit is een deelgraaf op evenveel toppen, zonder cykels en samenhangend). In deze boom kan je een wandeling construeren: teken de boom als een echte 'boom', dus met een wortel en takken die uitmonden in bladeren. Als je dan van de wortel vertrekt kan je heel eenvoudig een wandeling maken die terug uitkomt in de wortel, en waarbij elke boog tweemaal wordt aangedaan.
Om die boom te maken heb je een aantal bogen moeten wegdenken. Stel dat je boog ab hebt weggedacht, voeg die dan in je wandeling toe door, eens aangekomen in top a, de twee bogen ab,ba toe te voegen. Analoog voor alle andere bogen.
Op deze manier heb je een gesloten wandeling waarin elke boog tweemaal voorkomt, met weliswaar zeer veel herhalingen.
2. Uit het ongerijmde:
stel dat elke top graad minstens twee heeft; en toch bestaat er geen enkele wandeling die elke boog tweemaal gebruikt, en zonder herhalingen. (*)
Maar er bestaat minstens een wandeling met herhalingen: zie 1. Van al deze wandelingen noem je W de wandeling met het kleinst aantal herhalingen. Merk op dat, als W begint met ab en eindigt met ba, dat we dit ook een herhaling noemen.
Nu, stel dat we een herhaling hebben, dus ergens in de wandeling zit het stuk 'aba'. b heeft echter graad minstens twee, dus b moet nog elders in de wandeling voorkomen. Stel dat b nog voorkomt NA het stuk aba. (het geval VOOR is compleet analoog)
Dus we hebben: W = ...aba...b... Of nog: W = RabaSbT waarbij R,S,T wandelingen zijn. R eindigt niet op a of b, S begint noch eindigt op a of b, t begint niet met a of b, T eindigt op de beginletter van R.
Bekijk dan nu W' = RabS-1abT Hierin betekent S-1 dat we S in de omgekeerde richting doorlopen.
Deze W' heeft nu exact dezelfde herhalingen als W, behalve de boog ab, die wordt nu niet meer herhaald! Dus het aantal herhalingen is met één gezakt, terwijl we veronderstelden dat W de wandeling was met het laagste aantal herhalingen... Een strijdigheid, dus de onderstelling (*) is vals, wat het gestelde bewijst.
NB: achteraf bekeken moest dit geen bewijs uit het ongerijmde zijn: de techniek die van W een W' maakt en het aantal herhalingen met één reduceert, kan herhaald toegepast worden op de constructie uit 1., totdat alle herhalingen weg zijn. Die bewijsmethode is interessanter, omdat ze constructief is: het geeft je een methode om de gevraagde wandeling te construeren.
Een voorbeeld: beschouw de complete graaf op vier toppen a,b,c,d.
In stap 1. moet je hiervan een boom maken, doe dit door bd,bc en cd te schrappen.
De wandeling in de boom wordt: cadabac Voeg nu de weggelaten bogen weer toe: cbcdcadbdabac Herhaling cbc, ga dus op zoek naar een andere b in de wandeling, en keer het stuk tussen deze b's om: (ik kies de eerst b na de herhaling) cbdacdcbdabac Herhaling cdc, zoek dus nog een d en draai het stuk tussen de d's om (ik kies de d die NA de herhaling staat): cbdacdbcdabac Herhaling aba, zoek dus nog een b en draaien maar weer: cbdacdbadcbac En hier heb je je gevraagde wandeling!
