WisFaq!

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
16-6-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 (t₀=q, t₁, ..., t_n=r). We kunnen een kortste verbinding maken van s met een van de punten t_i op dit pad (eventueel kan s met t_i samenvallen). Dat betekent dat er vanuit het oorspronkelijke punt p drie disjuncte paden lopen naar t_i, 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.

Vriendelijke groet,

Zie DisWis - Grafentheorie [http://www.praktijk.nu/lesmateriaal/43/diswis-grafentheorie.html]

FvL
19-6-2015