(Problem 6.36 in the "4 Bills" book) Consider the integer program for the stable set problem in a graph G = (V, E): max EUEV ZU subject to 5 1 Vv,w EV such that vw e E Z WEV Find cutting plane proofs using sequences of C-G cuts (starting from the above system) for the following "combinatorial" family of cutting planes: (i) Let C be an odd cycle. It is easy to see that the maximum number of vertices from C in a stable set is at most . Thus, we have the family of "odd cycle inequalities" : EUEC to S -for all odd cycles C. (ii) The following graph is known as a 5-wheel. We have the "wheel inequalities" : Let W be the node set of a 5 - wheel with r as the center node. Then the following is a valid inequality for the integer points 2% + EveW\ } 2 2. (Convince yourself of the validity of the inequality using combinatorial arguments first) (iii) A set of vertices K C V forms a clique if there is an edge between every pair of vertices in K. Clearly, we can have at most one vertex from any clique; thus, we have the family of "clique" inequalities Evek zo