Exercise 2.15 (Edges joining adjacent vertices)

Proof. We demonstrate that

$\subseteq$

Let $z$ be such that $z=\lambda u+(1-\lambda )v$ for some $\lambda \in [0,1]$. Then, for all $i=1,\dots ,n-1$, we have

$$a_i^{\prime }z=a_i^{\prime }\left(\lambda u+(1-\lambda )v\right)=\lambda a_i^{\prime }u+(1-\lambda )a_i^{\prime }v=\lambda b_i+(1-\lambda )b_i=b_i.$$

$\supseteq$

Note that our edge is simply an intersection of a line and a polyhedron, i.e.,

$$P\bigcap \left\{z\in {\Re }^n\mid a_i^{\prime }z=b_i,i=1,\dots ,n-1\right\}.$$

Recall that an intersection of a line and a convex set must be a line segment by Exercise 2.10 (a), and as such it must have at most two extreme points. Since the basic feasible solutions $u,v$ are contained in this set, they are exactly the two extreme points we are talking about. But $\{z\in P\mid a_i^{\prime }z=b_i,i=1,\dots ,n-1\}$ is a convex bounded set; thus, by Theorem 2.9 it is the convex hull of its extreme points.