1.7

Counter-example graph G = (V,E):
V = {a, b, c, d, x, y₁, y₂, y₃, y₄}
E contains
 • the 4-clique on {a,b,c,d}: (a,b), (a,c), (a,d), (b,c), (b,d), (c,d)
 • edges (x,a), (x,b)
 • edges (x, y_i) for i = 1 … 4
(no other edges).

Degrees:
deg(x)=6 > deg(a)=deg(b)=4 > deg(c)=deg(d)=3 > deg(y_i)=1.

Algorithm’s behaviour (vertices processed in non-increasing degree order):
1. clique ← {x}.
2. a is adjacent to all in clique ⇒ clique ← {x,a}.
3. b is adjacent to all in clique ⇒ clique ← {x,a,b}.
4. c is NOT adjacent to x ⇒ rejected.
5. d is NOT adjacent to x ⇒ rejected.
All remaining vertices have degree 1 and are not adjacent to both x and a and b ⇒ rejected.

Algorithm outputs clique {x,a,b} of size 3, whereas the true maximum clique is {a,b,c,d} of size 4. Therefore the proposed heuristic is incorrect.

Back to Chapter 1