Comments on HW 6:

Exercise 1: 
Many students just didn't know how where to begin because they didn't
know how to apply Farkas Lemma. I would suggest looking at the
solutions if you were struggling on this problem.

After applying Farkas Lemma, you get a nonnegative constant y_0 in
your inequalities. You need to justify why setting y_0=1 is ok.

Exercise 3:
There were two ways to write this LP: either by translating
connectivity into an LP or by translating acyclicity into an LP. For
connectivity, writing "for all S a subset of V, sum_{e in E(S)} x_e =
|S|-1" is not correct. For S a proper subset of V, you need this to be
<= instead of =. In fact, you could have a spanning tree T such that
some proper subset S of vertices has no edges between the vertices in
S.

Note that you can't have strict inequalities in your LP, only weak
inequalities. So statements like sum_{i,j in S, {i,j} an edge} <|S|
should be written as sum_{i,j in S, {i,j} an edge} <= |S|-1.