Bewijs samenhangende graaf

"Bewijs dat in een samenhangende graaf de langste twee paden ten minste één punt gemeen hebben. Let wel, de langste 2 paden kunnen, maar hoeven niet, dezelfde lengte te hebben (het is zelfs mogelijk dat er vele paden even lang zijn als het langste pad)"

Bovenstaand bewijs moet gemaakt worden. Ik heb nu het volgende: bij een graaf met maximaal graad 2(dus zonder aftakkingen) heeft het langste pad en het één-na-langste pad altijd minstens 1 gemeenschappelijk punt. Dit is het punt met de hoogste graad.

Bij grafen met maximaal graad 3(dus met maximaal 1 aftakking per punt) heeft het langste pad en het één-na-langste pad ook altijd minstens 1 gemeenschappelijk punt, ook hier weer het punt met de hoogste graad.

Ik heb geen idee of ik ook maar een klein beetje goed zit... ik ben benieuwd! Alvast bedankt!

Pascal
Student universiteit - woensdag 16 april 2008

Antwoord

Beste PAscal,
Ik kan zo niet beoordelen of je bewijzen kloppen. Wat gebeurt er als er meerdere punten zijn van graad 3? Je bent zo te zien op weg naar een bewijs met volledig inductie....

Een andere aanpak zou kunnen zijn:
Teken alleen de twee langste paden. Als ze geen gemeenschappelijke punten hebben zijn ze disjunct. Maar de graaf is samenhangend, dus er moet een verbinding zijn tussen die paden. Kan je nu bewijzen dat er hierdoor langere paden ontstaan die wel minstens één punt gemeen hebben?

Succes,
Lieke.

ldr
vrijdag 18 april 2008

©2001-2024 WisFaq