graaf

Opgave - IrMO 2002 dag 1 vraag 2

Een graaf heeft $n$ toppen. Ieder punt heeft als graad maximum 3. Als er geen boog bestaat tussen twee punten, dan is er een derde punt dat met beide punten een boog gemeen heeft. Wat is de maximumwaarde van $n$? Wat is de maximumwaarde van $n$ als de graaf een driehoek bevat?

Oplossing

http://prime.problem-solving.be/activiteiten/breinbreker/nov-dec-2009

Stel je hebt 1 top met maximale graad 3. Elke buur van deze top kan nog hoogstens twee andere buren hebben. Dus nu kunnen er geen andere toppen meer zijn dan deze tien (1+3+6=10), want die zouden geen buur zijn van de eerste top en zouden er ook geen top mee gemeen hebben. Er zijn dus maximaal 10 toppen. De Petersen-graaf is een graaf die hieraan voldoet.

Stel dat de graaf een driehoek bevat. We nemen 1 van de toppen, noem A, uit de driehoek. Deze is verbonden met 2 toppen uit de driehoek en mogelijks nog een top B. Nu kunnen de twee overige toppen uit de driehoek nog elk maximum een buur hebben en kan B nog twee buren hebben. We hebben nu 8 toppen, meer kunnen het er niet zijn, want dan zou die geen buur zijn van zijn van A noch een top gemeen hebben met A. Dat 8 echt mogelijk is kan je makkelijk inzien door een tekening te maken ;)