Proving that a polyhedron has integer vertices 
Prove that the polyhedron $P =\{(x_1, \ldots , x_m, y) \in \mathbb R_{+}^{m+1}: y \leq 1,x_i \leq y \text{ for } i = 1, \ldots , m \} $ has integer vertices.

It seems obvious to me but don't know how to prove it. Any thoughts ?
 A: We would like to prove that the polyhedron
$$\mathcal P := \bigg\{ \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \in \mathbb R^{n+1} : \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \geq \begin{bmatrix} 0_n\\ 0\end{bmatrix}, \begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ y\end{bmatrix} \leq \begin{bmatrix} 0_n\\ 1\end{bmatrix} \bigg\}$$
is integral, i.e., it has integer vertices. Since the matrix is an upper triangular Frobenius matrix,
$$\begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix}^{-1} = \begin{bmatrix} \mathrm I_n & 1_n\\ 0_n^{\top} & 1\end{bmatrix}$$
which is also an integer matrix. Thus, the matrix is unimodular. Since it is also nonnegative,
$$\begin{bmatrix} \mathrm x\\ y\end{bmatrix} \leq \begin{bmatrix} \mathrm I_n & 1_n\\ 0_n^{\top} & 1\end{bmatrix} \begin{bmatrix} 0_n\\ 1\end{bmatrix} = \begin{bmatrix} 1_n\\ 1\end{bmatrix}$$
which allows us to conclude that $\mathcal P \subset [0,1]^{n+1}$, i.e., it is bounded. From Schrijver's book:



Thus, $\mathcal P$ is integral if and only if the $(n+1) \times (n+1)$ matrix
$$\begin{bmatrix} \mathrm I_n & -1_n\\ 0_n^{\top} & 1\end{bmatrix}$$
is totally unimodular. It is easy to prove by exhaustion that the matrix is indeed totally unimodular when $n \in \{1,2\}$. If we can prove that the matrix is totally unimodular also for $n \geq 3$, we then prove that $\mathcal P$ is integral. Chapters 19-21 of Schrijver's book should help.



*

*Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, July 1998.

