Graph/Färbung/Einfache Eigenschaften/Fakt/Beweis/Aufgabe

Zeige, dass die chromatische Zahl ${}\chi (G)$ eines Graphen ${}G=(V,E)$ die folgenden Eigenschaften erfüllt.

1. Ein Graph ist genau dann nicht leer, wenn seine chromatische Zahl ${}\geq 1$ ist.
2. Ein nichtleerer Graph besitzt genau dann die chromatische Zahl ${}1$, wenn er keine Kanten besitzt.
3. Ein Graph ist genau dann bipartit, wenn seine chromatische Zahl ${}\leq 2$ ist.
4. Es ist

   ${}\chi (G)\leq {\#\left(V\right)}\,.$

5. Der vollständige Graph ${}K_{n}$ besitzt die chromatische Zahl ${}n$.

Eine Lösung erstellen