# A full dimensional polyhedron has at least $n+1$ vertices

I'm stuck in a property when I was reading proof of a theorem about polyhedral theory:

Every full dimensional, bounded and non-empty polyhedron in $\mathbb R^n$ has at least $n+1$ vertices.

A vertex is a point of a polyhedron such that we cannot write it as $\lambda x+(1-\lambda)y$ such that $\lambda \in (0,1)$.

Can anyone give me a hint to prove this property? I think I should consider the fact that this polyhedron is convex hull its vertices and with induction I should prove that convex hull of every $k$ elements is at most a $k-1$ dimensional space. But it doesn't make sense to me also these properties. Could you please help me to understand these fact truly?

• Show you need $2$ points for $\mathbb{R}^1$ and then use induction on the number of dimensions. – David G. Stork Dec 2 '17 at 1:07
• Really, I don't know how to apply induction here. I know that every bounded polyhedron is a polytope and every polytope is convex hull of a set of vectors and if the number of these vectors is less than $n+1$ then it is contained in a hyperplane and hyperplane is not a full dimensional subset(its volume is zero). But I dont know to show that the vertices of the polyhedron is the generated set of this polytope! – GhD Dec 2 '17 at 1:15
• Two points determine a line segment (polytope in $\mathbb{R}^1$. If you want to make a polytope in $\mathbb{R}^2$, you need another point not on that line segment. In this way, $3$ points determine a polytope (triangular region) in $\mathbb{R}^2$. In order to make a polytope in $\mathbb{R}^3$, you need to add yet another point not in the triangular polytope. And, by induction, you need at least $n+1$ points to define a polytope in $\mathbb{R}^n$. – David G. Stork Dec 2 '17 at 1:24
• Dear Mr. Stork I think this way is not correct. For example when you have 2 points in $\mathbb R^1$ than it doesn't mean to add another point not on that line segment to have a polytope( really it is better to say bounded non empty and full dimensional polyhedron or polytope) in $\mathbb R^2$ because the first two points were not in $\mathbb R^2$. I think it is not mathematically true this way. – GhD Dec 2 '17 at 1:36
• You can embed the $2$ points in $\mathbb{R}^2$ and easily show that the resulting polyhedron is not "full dimensional" (as you state), and then add you additional point (properly) to show that the resulting polytope is full dimensional. – David G. Stork Dec 2 '17 at 2:12

## 1 Answer

Since you already know that a polyhedron is the convex hull of its vertices, the proof can proceed like this. Suppose the vertex set is $v_1, \dots, v_m$ with $m\le n$. The vectors $v_1-v_m,\dots, v_{m-1}-v_m$ span a linear subspace $W\subset \mathbb{R}^n$ of dimension at most $m-1$. Therefore, the points $v_1, \dots, v_m$ lie in the affine subspace $W+v_m$ of dimension at most $m-1 < n$. Since $W+v_m$ is a convex set, the convex hull of $v_1, \dots, v_m$ is contained in $W+v_m$ and therefore has empty interior.

• Thank you for your answer. I am not very familiar with this topic. Could you please introduce a book or some other sources about polyhedral theory to me to study? – GhD Dec 2 '17 at 14:03
• Anything with "convex hull" in it, like these notes – user357151 Dec 2 '17 at 15:06