WisFaq!

Kleurbaar, bipartiet, eulergraaf

Beste mensen,
De volgende vraagstukken heb geprobeerd te beantwoorden. Kunt u mij vertellen of ik in de juiste richting naar de antwoorden heb gezocht?
Alvast bedankt.
Rosita
vraag1 : bestaat een 26 reguliere niet bipartiete graaf die niet-Eulers is?
mijn oplossing : de graad is even en de stelling van Euler zegt dat een graaf dan en slechts dan een Euler graaf is als alle punten een even graad hebben dus de graaf is wel Eulers
vraag 2: Bestaat een 26 reguliere niet-bipartiete graaf die 2 kleurbaar is?
mijn oplossing: bestaat niet omdat alleen een bipartiete graaf 2 kleurbaar is.
vraag 3: bestaat een oneven gradige bipartiete volledige graaf?
mijn oplossing: graad van de graaf is oneven hij is dus 'oneven' regulier. Algemene vorm van een bipartiete graaf is Kn,m . Als hij regulier is dan is n = m.In dit geval is het niet zo.

Rosita
12-9-2008

Antwoord

Je oplossingen lijken me behoorlijk goed:

1. Ik dacht eerst dat dit juist was, maar: de stelling zegt dat een samenhangende graaf Eulers is dan en slechts dan als alle punten even graad hebben. Over samenhangend is hier niets gezegd. Het is dan niet zo moeilijk een tegenvoorbeeld te creëren: neem K₂₇ en zet er nog eens K₂₇ naast. Die graaf met 54 toppen is 26-regulier, niet-bipartiet en niet-Eulers want in een niet-samenhangende graaf kan je natuurlijk geen Eulercircuit maken.
2. Klopt helemaal.
3. Wat bedoel je met 'In dit geval is het niet zo'? Zelfs als n=m (wat volgens mij niet uit de opgave volgt^(*)) kan je nog altijd K_n,n bekijken: die is n-regulier, en bipartiet volledig. K_1,1 of K_3,3 zijn dus voorbeelden.

^(*) hangt af van wat je bedoelt met 'oneven gradig': betekent dit dat elke top een oneven graad heeft, of betekent het dat elke top dezelfde graad heeft en dat die graad oneven is (dus n-regulier met n oneven)? In die tweede interpretatie volgt dan inderdaad dat n=m.

Ook de formulering 'bipartiete volledige graaf' is nogal ongelukkig: waarschijnlijk bedoelt men inderdaad een K_n,m maar strikt genomen vraag je zo naar een volledige graaf K_n die ook nog eens bipartiet is. Hoedanook blijft K₂=K_1,1 een correct voorbeeld.

Groeten,
Christophe.

Christophe
15-9-2008