JFiZO - Lista 11

KLIKA_{nx} < KLIKA_{ny}

x, y ← (0,1)

Bierzemy instancję KLIKA_{nx} i konstruujemy instancję KLIKA_{ny} Jeśli x = y → trywialne

Jeśli x < y → w tym drugim potrzebujemy większej procentowo kliki
dokładamy w nim (y-x)n wierzchołków połączonych ze wszystkim
uzasadnienie:
(y-x)n + xn = yn czyli jeśli w nowym znajdziemy klikę rozmiaru yn to automatycznie mamy klikę xn w pierwotnym grafie.

Jeśli x > y → w tym drugim wystarczy mniejsza procentowo klika:
dokładamy (x-y)n izolowanych wierzchołków
uzasadnienie analogicznie