1. Review the IS to SUBSETSUM reduction from Lec 20. Specific tasks:
(a) Consider the cycle graph C5 on 5 vertices (a,b,c,d,e) with edges a-b, b-c, c-d, d-e, e-a (I suggest not to draw the graph). Take k=2. 
    * Find (S,T)=Reduce(C5,k).
    * If x,y do not have any edge in C5, then S has two numbers whose sum=T.
    * If S has some subset S' whose sum is T, then show how to obtain an independent set in G with k vertices.
(b) Find (S,T) = Reduce(C5,3). Ask students to explain why can't they find 3 numbers in S whose sum is T.

2. An anticlique of a graph G is a subset of vertices no two of which share an edge. Anticliques are also known as independent-sets.
Here are two problems related to anticliques.

AC: Given a graph G, and an integer k, decide if G contains a set V' of k vertices such that, every vertex in V' has no neighbor in V' (in other words, if u and v belong to V' then there cannot be edge between them).

ACX: Given  a graph G, and an integer k, decide if G contains a set V' of at least k vertices such that, every vertex in V' has at most one neighbor in V'.

Design a polynomial-time many-one reduction from AC to ACX and discuss its proof of correctness (state the correctness lemma precisely) and complexity.

3. almost3COL: Given an undirected graph G, is there a way to colour G using at most 3 colours such that at most 1 edge violate the colouring constraint (i.e., there can be at most 1 edge with same coloured endpoints).

Prove that almost3COL is NP complete. Show both (a) in NP, (b) NP-hardness.