Exercise: Let P ∈ R V be defined by the inequalities x u ≤ 1 for every u ∈ V , ( 1 ) x u + x v ≥ 1 for every edge u v ∈ E , ( 2 ) node set V = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }Starting from the system ( 1 ) − ( 2 ), give the cutting-plane proof of the inequality x 1 + x 2 + x 6 ≥ 2What I've tried: I know that I need to show that there exists a nonnegative combination from the inequalities ( 1 ) and ( 2 ) such that x 1 + x 2 + x 3 ≥ 3 holds. I don't know how unfortunately.Question: How do I solve this exercise?

Question

Exercise: Let   P  ∈        R    V   be defined by the inequalities                              x          u                ≤        1                               for every                       u            ∈            V            ,                                                  (        1        )                                      x          u                +                  x          v                ≥        1                               for every edge                       u            v            ∈            E            ,                                                (            2            )                              node set   V  =  {  1  ,  2  ,  3  ,  4  ,  5  ,  6  ,  7  ,  8  ,  9  }Starting from the system   (  1  )  −  (  2  ), give the cutting-plane proof of the inequality      x    1    +      x    2    +      x    6    ≥  2What I&#039;ve tried: I know that I need to show that there exists a nonnegative combination from the inequalities   (  1  ) and   (  2  ) such that       x    1    +      x    2    +      x    3    ≥  3 holds. I don&#039;t know how unfortunately.Question: How do I solve this exercise?

Krish Finley · Accepted Answer

If we put       x    1    =      x    2    =      x    6    =  1  /  2 and all other       x    i  ’s equal 1 then all the defining inequalities will be satisfied but       x    1    +      x    2    +      x    6    =  3  /  2  &amp;lt;  2.But the claim holds provided we require all xi are integer. Indeed, if       x    1    +      x    2    +      x    6    &amp;lt;  2 then al least two of these       x    i   (say,       x    u   and       x    v  ) are zero. Then   u  v  ∈  E, but       x    u    +      x    v    =  0, a contradiction to (2).

Exercise: Let P ∈ <mi mathvariant="double-struck">R V </msup>

Answered question

Answer & Explanation

New Questions in Algebra I