kann jemand wir zeigen, wie man diese Aufgaben lösen kann, da ich ein Testat habe und muss mich vorbereiten.
Danke
Wir fixieren einen unendlichen Graphen (V, E): Dieser besteht aus einer (abzählbar) unendlichen Menge V von “Punkten”
und aus einer Menge E ⊆ {{x, y}| x, y ∈ V, x ≠ y} von “Kanten” (die Punkte x und y sind “verbunden”, wenn {x, y} ∈ E
gilt). Der Graph (V, E) heißt k-färbbar, wenn es eine Funktion f : V → {1, . . . , k} gibt, sodass für alle x, y ∈ V gilt: Ist
{x, y} ∈ E so hat man f (x) ≠ f ( y). Um die Situation in der Aussagenlogik zu beschreiben, führen wir Aussagenvariablen
pxi für x ∈ V und i = 1, . . . , k ein. Intuitiv besagt pxi, dass der Punkt x die i-te Farbe zugewiesen bekommt.
1.) Man verwende Kompaktheit, um die folgende Aussage zu beweisen: Wenn (V0, {(x, y) ∈ E | x, y ∈ V0}) für eine
beliebige endliche Teilmenge V0 ⊆ V ein k-färbbarer Graph ist, dann ist der ganze Graph (V, E) ebenfalls k-färbbar
