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

An extreme point $p\in P$ cannot be written as a nontrivial convex combination of two distinct points of $P$: if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, then $u=v=p$.

A vertex of a linear polyhedron is a feasible point at which the active constraints include $n$ linearly independent row normals. Equivalently, some $n$ independent bounding hyperplanes intersect uniquely at that point. This definition does not require $P$ to be bounded or full-dimensional. For a linear polyhedron, it is also equivalent to the point uniquely maximizing a suitable linear function: sum the selected active inequalities to construct one such linear function.