0 Daumen
212 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community