Elke planaire graaf met 6 kleuren kan ingekleurd worden

Ik moet bewijzen dat elke planaire graaf 6-kleurbaar is (puntkleuring). Ik mag dit niet concluderen uit de 4- of 5-kleurbaarheid van planaire grafen. Ik denk dat ik het moet bewijzen met behulp van inductie maar ik heb werkelijk geen idee waar ik zou moeten beginnen, en het enige wat ik van inductie afweet is dat ik daar ooit één voorbeeld van heb gezien. Hopelijk zouden jullie me ermee kunnen helpen,
Alvast heel erg bedankt.

Tom Ja
Leerling bovenbouw havo-vwo - dinsdag 3 oktober 2006

Antwoord

Volgens mij kan op onderstaande website wel een idee krijgen waar je moet beginnen:

If we have six available colors, a vertex with only five neighbors obviously imposes no constraint on the coloring of the other vertices, because, regardless of the colors of its five (or fewer) neighbors, we can assign it a color without exceeding the six available colors. Therefore if we delete this vertex and all its connections from the graph, creating a graph with one fewer vertices, it's clear that if the resulting graph is 6-colorable, then so was the original graph. Moreover, Euler's formula assures us that this reduced graph also contains at least one vertex with five or fewer neighbors, so we can apply this procedure repeatedly, reducing the graph eventually to one with just 6 vertices, which is obviously 6-colorable. Hence the original graph is 6-colorable.

So, we've seen that Euler's formula immediately implies that no graph can require more than six colors.

Zie: The Four Color Theorem.

zondag 8 oktober 2006

©2001-2024 WisFaq