WisFaq!

Bogen kleuren in een graaf

Beste Wisfaq'ers

Ik heb een vraag die als volgt luidt:
Zij G een graaf waarin elke top graad 4 heeft. Toon aan dat je de bogen met 2 kleuren zodanig kan kleuren dat elke top op 2 bogen van de ene kleur en 2 bogen van de andere kleur ligt.

Als ik zulke grafen teken van 5 en 7 toppen, dan klopt dit inderdaad. Maar hoe bewijs je dat dit oneindig geldt?

Aangezien elke top een even graad heeft, zit er een eulercyclus in zulke grafen, kan ik daar iets mee?

Joeri
29-11-2013

Antwoord

Daar kun je inderdaad iets mee: kleur de takken in het Eulercircuit om en om rood en blauw.

kphart
29-11-2013