kompaktheit und färbarkeit von graphen

Question

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 6= 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) 6= 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.
(a) Man gebe eine Formelmenge Φ mit der folgenden Eigenschaft an: Es gilt I Φ genau dann, wenn es für jedes x ∈ V
genau ein i ∈ {1, . . . , k} mit I(pxi) = 1 gibt.
(b) Man gebe eine Formelmenge Ψ an, welche genau dann erfüllbar ist, wenn (V, E) ein k-färbbarer Graph ist.
(c) 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.

Answer 1

a) Sei

    φ_≥1(x) = ∨_i=1..k p_xi und

    φ≤1(x, i) = p_xi →∧_j=1..k,j≠i ¬p_xj.

φ_≥1(x) sagt aus, dass Knoten x minestens eine Farbe bekommt.

φ_≤1(x, i) sagt aus, dass wenn Knoten x die Farbe i bekommt, dass x dann keine andere Farbe bekommt.

Φ = ∪_{x∈V,i∈{1, ..., k}} {φ_≥1(x), φ_≤1(x, i)}.

b) Sei

    ψ(x, i) = p_xi→∧_{x,y}∈E ¬p_yi.

ψ(x, i) sagt aus, wenn der Knoten x die Farbe i hat, dann hat kein benachbarter Knoten die Farbe i.

Ψ = ∪_{x∈V,i∈{1, ..., k}} {ψ(x, i)} ∪ Φ.