integral polyhedron and projection

Question

Let $$P=\{x\in R^m: Ax=b, Bx\leq d, x\geq 0 \}$$ and $$Q=\{(x,y)\in R^{m+n}: Ax=b, Bx+y=d, x\geq 0, y\geq 0 \}$$ be given systems of linear inequalities. Assume $Q$ is an integral polyhedron with integral extreme points. It would seem to me that $P$ is the projection of $Q$ onto $x$-space. Can I conclude that $P$ is also integral?

Answer 1

Let $x$ be an extreme point of $P$ and let $y=d - Bx$, so that $(x,y)\in Q$. If $(x,y)$ is an extreme point of $Q$, integrality of $Q$ implies that $x$ is integer, so you just need to prove that $(x,y)$ is in fact an extreme point. Proof by contradiction is straightforward.