Eulerの多面体定理

$P$ の上で $c\cdot x\le\delta$、$G$ の上で $c'\cdot x\le\delta'$ とする。$P$ の頂点 $w$ のうち $G$ に属するものでは $c\cdot w=\delta$、$c'\cdot w\le\delta'$ であり、$G$ に属さないものでは $c\cdot w< \delta$ である。頂点は有限個なので、$\lambda>0$ を大きくとると、すべての頂点で $(c'+\lambda c)\cdot w\le\delta'+\lambda\delta$ となり、等号は $w\in G'$ のときに限る。$P$ は頂点の凸包なので（多面体 の定理「凸多面体は頂点の凸包」）、この不等式は $P$ 全体で成り立つ。等号の成り立つ $x\in P$ は、頂点の凸結合 $x=\sum\mu_kw_k$ で $\mu_k>0$ となる $w_k$ がすべて等号を満たし、$G'$ に属するので、凸集合 $G'$ に属する。逆に $G'$ の点では等号が成り立つ。よって $G'$ は $P$ の一般の面である。

後半：辺は $1$ 次元の有界な多面体なので線分で、その両端は辺の頂点だから、前半により $P$ の頂点である。面は平面に含まれる $2$ 次元の有界な多面体、すなわち凸多角形で、その頂点と辺は前半により $P$ の頂点と辺である。$\square$

段 1（$v$ の近くの形）。$P=\{x\mid a_j\cdot x\le b_j\ (j=1,\dots,m)\}$ とし、$a_j\cdot v=b_j$ となる $j$ の集合を $I$、$C:=\{y\mid a_j\cdot y\le0\ (j\in I)\}$ とおく。$P\subset v+C$ である。$I$ に属さない $j$ では $a_j\cdot v< b_j$ なので、半径 $r>0$ の球 $B$ を、その上で $a_j\cdot x< b_j$（$j\notin I$）となるように $v$ のまわりにとれる。$y\in C$ なら小さい $t>0$ で $v+ty\in B\cap(v+C)\subset P$ なので、$y\ne0$ なら $c\cdot y< 0$ である。$C$ と単位球面の共通部分はコンパクトなので、$\kappa>0$ があって $C$ の上で $c\cdot y\le-\kappa\|y\|$ である。$\varepsilon< \kappa r$ とすると、$(v+C)\cap\{c\cdot x\ge c\cdot v-\varepsilon\}$ の点は $B$ に入り、$P$ に属する。よって $P\cap\{c\cdot x\ge c\cdot v-\varepsilon\}=(v+C)\cap\{c\cdot x\ge c\cdot v-\varepsilon\}$ で、とくに $Q=(v+C)\cap H$ である。

段 2（1 の証明）。$y\in C$、$y\ne0$ について $s:=-c\cdot y/\varepsilon>0$ とおくと、$q:=v+y/s$ は $(v+C)\cap H=Q$ に属し、$v+y=v+s(q-v)$ である。$P\subset v+C$ なので、$P$ の点はこの形に書ける。$c\cdot(v+s(q-v))=c\cdot v-s\varepsilon$ なので、$c\cdot x\ge c\cdot v-\varepsilon$ となるのは $s\le1$ のときで、段 1 から $P\cap\{c\cdot x\ge c\cdot v-\varepsilon\}=\operatorname{conv}(\{v\}\cup Q)$ である。$P$ の内部の点 $p$ と、それを中心とする $P$ に含まれる球 $B(p,\rho)$ をとると、$0< t\le1$ について $v+t(B(p,\rho)-v)$ は $P$ に含まれる半径 $t\rho$ の球で、$t$ が小さければ $\{c\cdot x>c\cdot v-\varepsilon\}$ に入る。よって $\operatorname{conv}(\{v\}\cup Q)$ は平面に含まれず、$Q$ は直線に含まれない。$Q$ は平面 $H$ に含まれる有界な多面体なので、凸多角形である。

段 3（一般の面から $Q$ の一般の面へ）。$G$ を $v$ を含む一般の面とし、$P$ の上で $\ell\le0$、$G=P\cap\{\ell=0\}$ となる 1 次関数 $\ell$ をとる（$\ell(v)=0$）。$Q$ の上でも $\ell\le0$ なので $G\cap H=Q\cap\{\ell=0\}$ は $Q$ の一般の面である。$x=v+s(q-v)\in P$ について $\ell(x)=s\,\ell(q)$ なので、$x\in G$ は「$s=0$ または $q\in G\cap H$」と同値である。よって $\varphi\subset Q$ について $R(\varphi):=\{v+s(q-v)\mid s\ge0,\ q\in\varphi\}$ とおくと、$G=P\cap R(G\cap H)$ である（$R(\emptyset):=\{v\}$）。とくに $G$ は $G\cap H$ で決まり、$G\ne\{v\}$ なら $G\cap H\ne\emptyset$ である。

段 4（$Q$ の一般の面から一般の面へ）。$\varphi$ を $Q$ の空でない一般の面とし、$Q$ の上で $m\le0$、$\varphi=Q\cap\{m=0\}$ となる 1 次関数 $m$ をとる。$\ell(x):=m(x)-\frac{m(v)}{\varepsilon}(c\cdot x-c\cdot v+\varepsilon)$ は $H$ の上で $m$ に等しく、$\ell(v)=0$ である。$x=v+s(q-v)$ では $\ell(x)=s\,m(q)\le0$ なので、$P$ の上で $\ell\le0$ であり、$G:=P\cap\{\ell=0\}$ は $v$ を含む一般の面で $G\cap H=\varphi$ である。段 3 と合わせて全単射を得る。

段 5（包含と次元）。$G=P\cap R(G\cap H)$ から包含関係は両方向に保たれる。段 2 から $G\cap\{c\cdot x\ge c\cdot v-\varepsilon\}=\operatorname{conv}(\{v\}\cup\varphi)$（$\varphi=G\cap H$）であり、$G\subset R(\varphi)$ は $v$ と $\varphi$ の張るアフィン部分空間に含まれる。$v\notin H$ なので、その次元は $\dim\varphi+1$ で、$\operatorname{conv}(\{v\}\cup\varphi)$ はそれを張る。よって $\dim G=\dim\varphi+1$ である。

段 6（後半）。全単射により、$v$ を含む辺は $Q$ の頂点に、$v$ を含む面は $Q$ の辺に対応し、$e_i\subset f_j$ は $q_i\in f_j\cap H$ と同値である。凸多角形 $f_i$ の $v$ での $2$ 本の辺は $P$ の辺（lem-ep-face-of-face）で $v$ を含み $f_i$ に含まれるから、$q_i,q_{i+1}$ に対応する $e_i,e_{i+1}$ である。辺 $e=[v,w]$ を含む面はどれも $v$ を含み、$e\cap H$ を含む $Q$ の辺に対応するので、ちょうど $2$ 枚である（rem-ep-polygon）。$\square$