Proving the pigeonhole principle in Cutting Planes Exercise 3 from https://massimolauria.net/courses/2015.ProofComplexity/lecture6.pdf


  Consider the set of inequalities $x_i+x_j\leq1$ for $1\leq i&lt;j\leq n$.
  
  Find a derivation of $\sum_{i=1}^n x_i\leq 1$ in $O(n^2)$ length.


If it were just algebra I could just show by contradiction that at most one $x_i$ could be 1 and be done but how does it translate it into cutting planes PS? I guess a similar idea would be by obtaining $\sum_{i=1}^n x_i \leq n-1 -(n-2)x_i$ for all $i$ through addition of $x_i+x_j$ for all $1\leq j\leq n$ but I'm stuck there. 

Thanks for your help.
The proof is by induction. Here is the inductive step.

Suppose that we know both of the following inequalities:
$$
x_1 + \cdots + x_m \leq 1 \\
x_2 + \cdots + x_{m+1} \leq 1
$$
Add them to get
$$
x_1 + 2x_2 + \cdots + 2x_m + x_{m+1} \leq 2
$$
Add the axiom $x_1 + x_{m+1} \leq 1$ to get
$$
2x_1 + \cdots + 2x_{m+1} \leq 3
$$
Divide by 2 and round down to get
$$
x_1 + \cdots + x_{m+1} \leq 1
$$
I'll let you fill in the remaining details.