Ein (einfacher, unendlicher) Graph \( G=(V, E) \) ist vierfärbbar, falls es eine Färbung \( c: V \rightarrow\{0,1,2,3\} \) der Knoten gibt, sodass für alle Kanten \( (u, v) \in E \) gilt: \( c(u) \neq c(v) \).
Ein endlicher Teilgraph \( G^{\prime} \) von \( G \) ist \( G^{\prime}=\left(V^{\prime}, E^{\prime}\right) \), sodass \( V^{\prime} \subseteq V \) mit \( \left|V^{\prime}\right|<\infty \) und \( E^{\prime} \subseteq V^{\prime} \times V^{\prime} \cap E \)
Zeigen Sie: Ein Graph ist vierfärbbar genau dann, wenn jeder endliche Teilgraph vierfärbbar ist.
