Proposition 2.3
Let \(P \subseteq \mathbb{R}^d\) be a polytope, and \( \begin{align*} V := \operatorname{vert}(P) \end{align*} \). Let \(F\) be a face of \(P\).
  1. The face \(F\) is a polytope, with \(\operatorname{vert}(F)=F\cap V\).
  2. Every intersection of faces of \(P\) is a face of \(P\).
  3. The faces of \(F\) are exactly the faces of \(P\) that are contained in \(F\).
  4. \(F=P\cap\operatorname{aff}(F).\)

Proof (iii):
Let \(G \subseteq F\) be a face in \(P\) be defined by the valid inequality \(bx \leq b_0\). Then

$$ \begin{align*} G = P \cap \{ x \in \mathbb{R}^d \mid bx = b_0 \}. \end{align*} $$

But \(G \subseteq F\) and \(F \subseteq P\). Hence

$$ \begin{align*} G = F \cap \{ x \in \mathbb{R}^d \mid bx = b_0 \}. \end{align*} $$

Thus, \(G\) is also a face in \(F\). Conversely, let \(F\) be a face in \(P\) defined by the inequality \(cx \leq c_0\) so

$$ \begin{align*} F = P \cap \{ x \in \mathbb{R}^d \mid cx = c_0 \}. \end{align*} $$

and let \(G\) be a face in \(F\) defined by the inequality \(bx \leq b_0\) so

$$ \begin{align*} G = F \cap \{ x \in \mathbb{R}^d \mid bx = b_0 \}. \end{align*} $$

Note that every point in \(F\) satisfies \(bx \leq b_0\). We want to show that \(G\) is a face in \(P\). To do this, let \(V_0 = \operatorname{vert}(F)\) and let \(V_1 = V \setminus V_0\). Furthermore, assume that \(F \neq P\) so \(V_1\) is not empty. \
Take any point \(x\) in \(F\) and let \(\lambda\) be any real number. Since \(cx = c_0\), then we can multiply \(\lambda\) on each side to get

$$ \begin{align*} \lambda (cx) = \lambda c_0. \tag{1} \end{align*} $$

Moreover, we know that \(x\) satisfies \(bx \leq b_0\) so we can add \(\lambda (cx)\) to both sides to get

$$ \begin{align*} bx + \lambda (cx) &\leq b_0 + \lambda (cx) \\ bx + \lambda (cx) &\leq b_0 + \lambda c_0 \quad \text{(by (1))} \\ (b+ \lambda c)x &\leq b_0 + \lambda c_0. \tag{2} \end{align*} $$

We want to show that any point in \(P\) also satisfies it. Recall that by Proposition 2.2, \(P = \operatorname{conv}(V)\). Hence it suffices to show that the inequality is satisfied by any point in \(\operatorname{V}\). So let \(v \in V\). If \(v \in V_0\), then \(v \in F\) so (2) holds. If \(v \in V_1\), then we want to show

$$ \begin{align*} (b+ \lambda c)v &\leq b_0 + \lambda c_0 \end{align*} $$

Solve for \(\lambda\) to get

$$ \begin{align*} b_0 + \lambda c_0 &\geq bv + \lambda cv \\ \lambda c_0 - \lambda cv &\geq bv - b_0 \\ \lambda (c_0 - cv) &\geq bv - b_0. \end{align*} $$

But recall that \(v \in V_1\) so \(v \not\in F\). Hence \(c_0 > cv\) is a strict inequality and we can divide both sides by \((c_0 - cv)\) to get

$$ \begin{align*} \lambda &\geq \frac{bv - b_0}{c_0 - cv}. \end{align*} $$

To make this work for all vertices in \(V_1\), choose \(\lambda\) such that

$$ \begin{align*} \lambda &> \max_{v \in V_1} \left\{ \frac{bv - b_0}{c_0 - cv} \right\} \end{align*} $$

With this choice of \(\lambda\), we get that (2) is a valid inequality for any point in \(P\). This implies that it defines a face

$$ \begin{align*} K = P \cap \{ x \in \mathbb{R}^d \mid (b+ \lambda c)x &= b_0 + \lambda c_0 \}. \end{align*} $$

We claim that \(G = K\). Take \(x \in G\). So \(x\) satisfies \(bx = b_0\). Moreover, since \(G \subseteq F\), then \(x \in F\). Therefore, \(cx = c_0\). Hence

$$ \begin{align*} (b+ \lambda c)x &= bx + \lambda cx = b_0 + \lambda c_0. \end{align*} $$

Thus, \(x \in K\) and \(G \subseteq K\). Conversely, let \(x \in K\). Then by definition

$$ \begin{align*} (bx + \lambda c)x &= b_0 + \lambda c_0 \\ bx + \lambda cx &= b_0 + \lambda c_0. \tag{3} \end{align*} $$

Next, we want to show that \(x \in F\). Since \(K\) is a face in \(P\), then we know by Proposition 2.3(i), \(K = \operatorname{conv}(\operatorname{vert}(K))\). If \(v \in V_1\), then by the choice of \(\lambda\),

$$ \begin{align*} (b + \lambda c)v < b_0 + \lambda c_0. \end{align*} $$

Therefore, no vertex in \(V_1\) belongs to \(K\). This implies that \(\operatorname{vert}(K) \subseteq V_0\). But we know that \(F = \operatorname{conv}(V_0)\). Hence \(K \subseteq F\). Because \(x \in F\), we have \(cx = c_0\). Substituting in (3)

$$ \begin{align*} bx + \lambda c_0 &= b_0 + \lambda c_0 \\ bx &= b_0. \end{align*} $$

Since \(x \in F\) and \(bx = b_0\), we have \(x \in G\). Therefore, \(K \subseteq G\). Finally, we conclude that \(G = K\), proving that \(G\) is a face of \(P\). \(\ \blacksquare\)

References