## Caratheodory’s Theorem on Convex Hulls

Caratheodory’s theorem states that if a point is in the convex hull of , then there is a subset consisting in at most elements such that lies in the convex hull of .

**Proof:** Take in the convex hull of . Then is a convex combination of a finite number of points in , i.e. there exist and such that and

If then there is nothing to prove. Suppose that . Then the points are linearly dependent (more than points in are always linearly dependent), i.e. there exist , not all zero, such that

Define , and note that we have

and

Since not all are zero, we can assume without losing generality that there exists a . Then we have for any

Pick . Then all the coefficients are positive and one of them is zero. Moreover, their sum is

Therefore we have reduced to a convex combination of elements of . We can repeat the procedure as long as .