ITT0030 Diskreetne matemaatika II - eksamikonspekt
taandatav graafde värvimise
ülesandele: (tähistades
erinevad riigid kaardil graafi G
tippudega ning piirid riikide
vahel servaega).
Neljavärvi probleemi lahendus: Iga tasandiline graaf G=(V,E) on värvitav 4 värviga.
,,Probleemiks" ongi neljavärviprobleemi puhul see, et ,,lahendust" pole kunagi suudetud
ammendavalt tõestada. Selle kohta on küll vigaseid - ning arvuti ,,proof by exhaustion"-tüüpi
tõestuseid, ent konkreetne matemaatiline tõestus puudub tänaseni. (Arvuti tõestused:
G.Gonthier, 2002).
Enamik kaarte on tegelikult värvitavad lausa 3 värviga, neljandat värvi on tarvis siis, kui üks
annaabi.ee 
