We saw in lecture the model below to describe find the largest independent set of nodes of a graph (recall an independent set of nodes means no two vertices in the set are adjacent). This problem has a formulation with a variable xi for each node maxX i xi xi + xj 1 for each arc (i,j) xi 0 xi 1 a) A clique of a graph is a complete subgraph (all vertices are connected). Prove that each clique gives a valid cut for the independent sets of a graph. These are called clique inequalities. b) Show that all clique inequalities are actually Chvatal-Gomory cuts.

8. Cuts for the Stable set problem (5pts) We saw in lecture the model below to describe find the largest independent set of nodes of a graph (recall an independent set of nodes means no two vertices in the set are adjacent). This problem has a formulation with a variable Xi for each node max Xi X; + x; 0 Xi 0 Xi