Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 2 / a / iii / Solution

Let $p$ be a vertex of a linear polyhedron and choose $n$ independent active constraints, written $Bp=d$, with $B$ invertible. Suppose $p=\lambda u+(1-\lambda )v$, where $u,v\in P$ and $0<\lambda <1$. Each selected inequality has $B_{i}u\le d_i$ and $B_{i}v\le d_i$, whileSince both weights are positive, equality in this weighted upper bound forces $B_{i}u=B_{i}v=d_i$ for every selected row. Hence $Bu=Bv=d$, and invertibility gives $u=v=p$. Therefore every vertex of a linear polyhedron is an extreme point.