Satz von Grötzsch (Graphentheorie)
# Satz von Grötzsch (Graphentheorie)

In der Graphentheorie, einem Teilgebiet der Mathematik, ist der Satz von Grötzsch ein auf Herbert Grötzsch zurückgehender Satz über die Färbbarkeit von Graphen mit drei Farben.

## Färbbarkeit

Eine Färbung ordnet jedem Knoten eines Graphen eine Farbe zu, so dass die Knoten jeder Kante mit jeweils unterschiedlichen Farben gefärbt werden. Man interessiert sich für die minimale Anzahl an Farben, die für die Färbung eines gegebenen Graphen notwendig ist. Der Vier-Farben-Satz besagt, dass sich jeder planare Graph mit vier Farben färben lässt. Der Satz von Grötzsch beantwortet die Frage, welche planaren Graphen sich sogar mit drei Farben färben lassen.

## Satz von Grötzsch

Ein dreiecksfreier planarer Graph kann mit drei Farben gefärbt werden.

(Ein Graph heißt dreiecksfrei, wenn er keinen zum vollständigen Graphen $K_{3}$ isomorphen Teilgraphen enthält.)

