Hamiltongraaf

Ik moet een tweedelige vlakke graaf tekenen. Maar dit lukt me niet met de volgende voorwaarden:
- het geen eulergraaf maar wel een hamiltongraaf is
- het moet bestaan uit meer dan 10 punten.

Kan dit wel?

Troy
Iets anders - donderdag 6 juni 2019

Antwoord

Neem de cyklische graaf met twaalf punten, genummerde als de uren op een klok. Verbind ook nog de punten 1 en 11, en ook 5 en 7. Er is een hamiltoncykel: loop de klok rond, de graaf is geen Eulergraaf (vier punten van graad drie) en het kleurgetal is $3$.

kphart
donderdag 6 juni 2019

Re: Hamiltongraaf

©2001-2024 WisFaq