Give the cutting-plane proof of the inequality $x_1+x_2 + x_6 \geq 2$

Question

Exercise: Let $P\in\mathbb{R}^V$ be defined by the inequalities $$\begin{split}x_u \leq 1 &\text{ for every $u\in V,$}\,\,\,(1)\\x_u + x_v \geq 1 &\text{ for every edge $uv\in E,\,\,\, (2)$}\end{split}$$In the image, you see a 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 \geq 2$$

What 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\geq 3$ holds. I don't know how unfortunately.

Question: How do I solve this exercise?

Thanks in advance!

Answer 1

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<2$.

But the claim holds provided we require all $x_i$ are integer. Indeed, if $x_1+x_2+x_6<2$ then al least two of these $x_i$ (say, $x_u$ and $x_v$) are zero. Then $uv\in E$, but $x_u+x_v=0$, a contradiction to (2).