3 reguliere graaf: bewijzen dat er altijd een cykel met even lengte bestaat
Ik wil bewijzen dat een 3 reguliere graaf g=(v,e) altijd een cykel van even lengte bevat. Je kunt niet aannemen dat de graaf samengesteld is toch? Als hint wordt gegeven dat je kunt kijken naar het langste pad: Het startpunt heeft graad drie, 'wat betekent dit?' Ik had bedacht dat het langste pad altijd door alle punten kan gaan in een drie reguliere graaf en dus lengte |v| - 1 heeft, hebben we hier wat aan?
Lisa
Student universiteit - dinsdag 16 juni 2015
Antwoord
Hallo Lisa,
Laten we er vanuit gaan dat de graaf samenhangend is, kies zonodig een samenhangende deelgraaf.
Kies een punt p van de graaf, zodanig dat de graaf samenhangend blijft als het punt wordt verwijderd. Punt p was verbonden met drie punten, zeg q, r en s. Aangezien de graaf zonder p nog steeds samenhangend is, is q verbonden met r via een pad (t0=q, t1, ..., tn=r). We kunnen een kortste verbinding maken van s met een van de punten ti op dit pad (eventueel kan s met ti samenvallen). Dat betekent dat er vanuit het oorspronkelijke punt p drie disjuncte paden lopen naar ti, via q, via r en via s. Van deze drie hebben er ofwel twee even lengte, ofwel twee oneven lengte (duiventilprincipe). Een dergelijk tweetal laat zich combineren tot een cykel van even lengte.
